Curriculum vitae
Arne Andersson
Computing Science Department
Information Technology
Uppsala University
Box 311
SE  751 05 Uppsala
Sweden
Office location: Polacksbacken, Building 1, room 306
Phone at work: (+46) 18  471 10 22
Mobile phone: (+46) 704  25 03 82
Fax: (+46) 18  51 19 25
Email: arnea@csd.uu.se
Home address: Rödhakevägen 3B, Uppsala
Phone at home: (+46) 18  32 44 45
Personal data

Born in Västervik, Sweden, December 7, 1957.

Married to Kerstin Andersson, 1989.

Two daughters: Kajsa, born 1992, and Stina, born 1994.
Education and exams

1976: High School Degree (studentexamen).

1981: Teacher's Certificate maths/physics/chemistry.

198384: Undergraduate courses in computer science.

1990: Ph.D. degree.

1994: Appointed to ``docent''.
Senior Academic Positions

199092: Researcher, Lund University.

199297: Research assistant, Lund University.

199798: Associate professor, Lund University.

1998...: Professor, chairholder, Uppsala University.
Leave of absence etc

19921993 one year, 80% parental leave.

July 2000  November 2001: &0% leave for working in industry (founding the company Trade Extensions)

2002... Minor partial leave for working in industry.
Academic Awards
1991: Awarded the ``Best Teacher at Lund University''prize by the
students.
Visiting post docs
Erisk Schenk 19961997.
Teaching and advising

198182: Teacher (maths and physics) at Söderkullaskolan, Malmö (Junior High School).

198283: Teacher (maths, physics and chemistry) at Tunaskolan, Lund (Junior High School).

198384: Teacher (maths, physics, programming and systems science) at Polhemskolan, Lund (Senior High School).

198598: Teacher (all levels) at the Department of Computer Science, Lund University:
full responsibility for major courses, including making and correcting exams;
responsibility for the development
of a major course in algorithms, data structures and programming methodology; full responsibility for redevloping a beginner's course in computer science;
full responsibility for the development and
teaching of graduate courses on pattern recognition,
machine learning and resource allocation,
advisor of numerous diploma works and maters theses.

1993: Developed a demonstration program for algorithm animation.

199193: Teaching consultant at SATTCONTROL, Malmö.

1991...: Advisor for Ph.D. students.
Main advisor for Ph.D. Students
 Stefan Nilsson: Licenciat Thesis 1995, Ph.D. Thesis 1996.

Kurt Swanson: Licenciat Thesis 1996, Ph.D. Thesis 1998.

Fredrik Ygge was coadvised by me.
He defended his Ph.D. thesis 1998.

Jesper Larsson: Licenciat Thesis 1998,
Ph.D. Thesis 1999.

Maria Karlsson Licenciat Thesis 2003.

Per Carlsson: Licenciat Thesis 2001, Ph.D. 2005.

Jim Wilenius: Ph.D.planned 2008.
Active coadvisor for Ph.D. Students

Fredrik Ygge: Ph.D. Thesis 1998.

Kent Sxain: Licenciat Thesis, 2001.
>li>
Markus Bylund: Licenciat Thesis 2001.

Kidane Asrat: Licenciat Thesis 2003, Ph.D. 2005.
Administration

197980: Member of the education sectional board (``linjenämnden matnat''), Lund University.

198790, 199498: Member of the board of the Department of Computer
Science and Numerical Analysis, Lund University.

198990: Member of the Faculty sectional board (``sektionsnämnden, matematikfysik''), Lund University.

199798: Chairman of Department of Computer Science and Numerical Analysis, Lund University.

1998: Chairman of Computing Science Department, Uppsala University.

19992000: Chairman of Department of Information Technology, Uppsala University,
and chairman od the Computing Science Department (a subdepartment within IT).

20022003 Head of research (forskningsprefekt) at Department of Information Technology.

2002... Chairman of Computing Science Department, subdepartment of the IT department.
Visiting Positions

1994: Guest Professor at Universität Freiburg, 1 month;

19971998: Parttime Professor at BRICS center in Aarhus, a total of two months
in 1997, spread over the year, a total of one month
during 1998.
Invited Speaker

1996: Invited speaker at SWAT'96;

1996: Invited speaker at Annual International Seminars on the Teaching
of Computing Science at University Level, ICL/University of Newcastle;

Invited speaker at Workshop on Combinatorial auctions, Internation Symp on Mathematical Programming, 2003.

Numerous presentations at universities, research institutes, and companies.
Grants

19921994: TFR grant ``Efficient Methods for Sorting and Searching''.

19941997: TFR grant ``Efficient Data StructuresEfficient Software''.

19982000: TFR grant ``Efficient Data StructuresEfficient Software''.

19982001: NUTEK grant ``Techniques for Distributed Markets, Negotiation, and
Resource Allocation''.
 20022005 Research grant from Sydkraft.
 20022005 Research grant from VR "Algorithms for Advanced Negotiations".
Others

1989 Refereeing for several journals like SIAM Journal of Computing,
Acta Informatica, SoftwarePractice and Experience, Information Processing Letters, Journal of Algorithms, BIT/Nordic Journal of Computing, IEEE Transactions on Computers, and for conferences like ICALP, SWAT, WADS, STOC, STACS;

1992: Member of examination committee for a Ph.D. thesis in radiation physics
(including computer science aspects), Lund University;

1993: Member of organising committee for ICALP 93;
1994: External examiner for an Australian Ph.D. thesis in computer science;

1995: Member of examination committee for a Ph.D. thesis in computer science,
Lund Institute of Technology;

1996: Opponent, Ph.D. thesis in computer science at Odense University;

1997: Opponent, Ph.D. thesis in computer science at Aarhus University;

1997: External member of appointment board for associate professor
position in Odense

1997: Member of program committee for WADS 97.

19912000: Invited to all Dagstuhl Seminars on Data Structures.

1997: Invited to Oberwolfach seminar on Efficient Algorithms

1997: Opponent, Licenciat thesis, KTH, Stockholm

1998: Member of examination committee for a Ph.D. thesis in computer systems,
Uppsala University

1999: Member of program committee for WADS 99.

1999: Member of examination committee for a Ph.D. thesis in computer systems,
Uppsala University

1999: Opponent, Ph.D. thesis in computer science, Copenhagen University;

1999: Member of examination committee for a Ph.D. thesis in
Information Theory, Lund University.

1999: Opponent, Ph.D. thesis in computer science, Helsinki University;

1999: External member of appointment board for associate professor
position in bioinformatics at KTH, Stockholm

1999: Member of examination committee for a Ph.D. thesis in
Computer Science, KTH.

2000: Member of examination committee for a Ph.D. thesis in
Computer Science, KTH.

2000: Member of examination committee for a Ph.D. thesis in
Bioinformatics, Uppsala University.

2000: External member of appointment board for associate professor
position at Linköping University

2000: External member of nomination board for five full professors
at KTH, Stockholm

2000: Opponent, Ph.D. thesis in computer science, Aarhus University;

After 2000: Member of numerous evaluation committees, Ph.D. committees, etc.
Among others, member of an internation evaluation committee for two new Danich ITuniversities, member of program committee form FCT/TCS 2003 and SWAT 2004.
Industrial Experience
Cofounder of Trade Extensions, a company dealing with advanced electronic negotiations.
The company was founded in 2000.
Publications
Ph.D. thesis

A.Andersson.
Efficient Search Trees.
Ph.D. Thesis, Lund University, Sweden, 1990.
Journals

A. Andersson, Ch. Icking, R. Klein, and Th. Ottmann.
Binary search trees of almost optimal height.
Acta Informatica, 28:165178, 1990.

A. Andersson and S. Carlsson.
Construction of a tree from its traversals in optimal time and space.
Information Processing Letters, 34(1):2125, 1990.

A. Andersson.
A note on the expected behaviour of binary tree traversals.
Computer Journal, 33(5):471472, 1990.

A. Andersson.
Maintaining alphabalanced trees by partial rebuilding.
International Journal of Computer Matehmathics, 38:3748, 1990.

A. Andersson.
A note on searching in a binary search tree.
SoftwarePractice and Experience, 21(10):11251128, 1991.

A. Andersson.
Comments on ``On the balance property of patricia tries: External
path length viewpoint''.
Theoretical Computer Science, 106:391393, 1992.

A. Andersson and S. Nilsson.
Improved behaviour of tries by adaptive branching.
Information Processing Letters, 46:295300, 1993.

A. Andersson and S. Nilsson.
Efficient implementation of suffix trees.
SoftwarePractice and Experience, 25(2):129141, 1995.

A. Andersson and Th. Ottmann.
New tight bounds on uniquely represented dictionaries.
SIAM Journal of Computing, 24(5):10911103, 1995.
A preliminary version appears in Proc. 32nd IEEE Sympos.
Foundations of Computer Science, IEEE Computer Society Press, 1991.

A. Andersson and A. Brodnik.
Comments on SelfIndexed Sort.
SIGPLAN Notices , 38(8), 1996.

A. Andersson and K. Swanson.
On the difficulty of range searching.
Computational Geometry: Theory and Applications , 8(3):115122,
1997.

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman.
Sorting in linear time?
Journal of Computer and System Sciences, vol 57, pp 7493, 1998.

A. Andersson and O. Petersson.
Approximate Indexed Lists.
Journal of Algorithms 29:256276, 1998.

A. Andersson and S. Nilsson.
Implementing radixsort.
The ACM Journal of Experimental Algorithmics. Volume 3,
Article 7, 1998.

A. Andersson.
General balanced trees.
Journal of Algorithms, 30: 128, 1999.

A. Andersson, P.B. Miltersen, and M. Thorup.
Fusion trees can be implemented with AC0 instructions.
Theoretical Computer Science, vol 215, pp 337344, 1999.

A. Andersson, N. J. Larsson, and K. Swanson.
Suffix trees on words.
Algorithmica 23, 1999.

A. Andersson, P. Davidsson, and J. Linden,
Measurebased performance evaluation.
Pattern recognition in practice, 1999.

A. Andersson, F. Ygge,
Efficient resource alloctaion with nonconcave objective functions.
Computational Optimization and Applications, 20:281298, 2001.

Per Carlsson, Fredrik Ygge, and Arne Andersson,
Extending Equilibrium Markets.
IEEE Intelligent Systems, vol.16, July/August 2001.

Arne Andersson, Torben Hagerup, Johan Håstad, and Ola Petersson,
Tight Bounds for Searching a Sorted Array of Strings
SIAM Journal on Computing
Volume 30, Number 5
pp. 15521578, 2001.

Arne Andersson, Per Carlsson, and Fredrik Ygge.
Resource Allocation With Wobbly Functions.
Computational Optimization and Applications,
23,
2,
pp. 171200, 2002.

Arne Andersson, Mikkel Thorup.
Dynamic Ordered Sets with Exponential Search Trees.
Journal of the ACM, 2007.

Maria Karlsson, Fredrik Ygge, and Arne Andersson.
MarketBased Approaches to Optimization.
Computational Intelligence, 2007.

Per Carlsson, Arne Andersson.
A flexible model for treestructured multicommodity markets.
Electronic Commerce Research, vol 7, no 1, March 2007.
Refereed conferences

A. Andersson.
Optimal bounds on the dictionary problem.
In Proc. Symposium on Optimal Algorithms, pages 106114.
Springer Verlag, 1989.

A. Andersson.
Improving Partial Rebuilding by Using Simple Balance Criteria,
In Proc. Workshop on Algorithms and Data Structures,
Lecture Notes in Computer Science 382, Springer Verlag,
pages 393402, 1989.

A. Andersson and T. W. Lai.
Fast updating of wellbalanced trees.
In Proc. Scandinavian Workshop on Algorithm Theory, pages
111121. Springer Verlag, 1990.

A. Andersson and T. W. Lai.
Comparisonefficient writeoptimal searching and sorting.
In Proc. 2nd ann. International Symposium on Algorithms,
pages 273282. Springer Verlag, 1991.

A. Andersson and Th. Ottmann.
Faster Uniquely Represented Dictionaries.
In Proc. 32nd IEEE Sympos. Foundations of Computer Science,
pages 642649, 1991.

A. Andersson.
Balanced search trees made simple.
In Proc. Workshop on Algorithms and Data Structures, pages
6071. Springer Verlag, 1993.

A. Andersson and Ch. Mattsson.
Dynamic interpolation search in o(loglog n) time.
In Proc. 20th International Colloquium on Automata,
Languages and Programming. Springer Verlag, 1993.

A. Andersson, T. Hagerup, J. Håstad, and O. Petersson.
The complexity of searching a sorted array of strings.
In Proc. 26th ACM Symposium on Theory of Computing, pages
317325. ACM Press, 1994.

A. Andersson and S. Nilsson.
Faster searching in tries and quadtreesan analysis of level
compression.
In Proc. 2nd Annual European Symposium on Algorithms,
pages 8293. Springer Verlag, 1994.

Arne Andersson and Stefan Nilsson.
A new efficient radix sort.
In Proc. 35th Annual IEEE Symposium on Foundations of
Computer Science, pages 714721. IEEE Computer Society Press, 1994.

A. Andersson and O. Petersson.
Online approximate list indexing with applications.
In Proc. 6th Annual ACMSIAM Symposium on Discrete
Algorithms, pages 2027, 1995.

A. Andersson and K. Swanson.
On the difficulty of range searching.
In Proceedings of the 4th Workshop on Algorithms Data
Structures, volume 955, pages 473481. Springer Verlag, 1995.

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman.
Sorting in linear time?
In Proceedings 27th ACM Symposium on Theory of Computing,
pages 427436. ACM Press, 1995.

A. Andersson, J. Håstad, and O. Petersson.
A tight lower bound for searching a sorted array.
In Proc. 27th ACM Symposium on Theory of Computing, pages
417426. ACM Press, 1995.

A. Andersson.
Sublogarithmic searching without multiplications.
In Proc. 36th IEEE Symposium on Foundations of Computer
Science, pages 655663. ACM Press, 1995.

A. Andersson.
Faster deterministic sorting and searching in linear space.
In Proc. 37th IEEE Symposium on Foundations of Computer
Science, 1996.

A. Andersson, P.B. Miltersen, S. Riis, and M. Thorup.
Static dictionaries on ACO RAMS: Query time
Theta(sqrt(log n/loglog n)) is necessary and sufficient.
In Proc. 37th IEEE Symposium on Foundations of Computer
Science, 1996.

A. Andersson, N. J. Larsson, and K. Swanson.
Suffix trees on words.
In Proc. Combinatorial Pattern Matching, 1996.

A. Andersson and S. Nilsson.
Implementing radixsort.
In Proc. Workshop on Algorithm Engineering, WAE '97, 1997.

A. Andersson and F. Ygge.
Managing largescale computational markets.
In Proc. 31st Hawaiian International Conference on System Sciences,
VOL VII  Software Technology Track,
pages 4  13, IEEE Computer Society, 1998. (Winner of the best paper award of the Software Technology Track)

A. Andersson, P. Davidsson, and J. Linden.
Model selection using measure functions
Proc. of the ECML'98 Workshop on Upgrading Learning
to the MetaLevel: Model Selection and Data Transformation,
pages 5465, 1998.

Fredrik Ygge, Hans Akkermans, Arne Andersson, Marko Krejic, and Erik Bortjes.
The HomeBots System and Field Tests:
A MultiCommodity Market for Predictive
Load Management
Proccedings of the Fourth International Conference
and Exhibition on The Practical Application of
Intelligent Agents and MultiAgents (PAAM99), London, UK, 1999.

A. Andersson, M. Tenhunen, and F. Ygge.
Integer Programming for Combinatorial
Auction Winner Determination.
Proc. of the
Fourth International Conference on Multiagent Systems (ICMAS00), 2000.

A. Andersson and M. Thorup.
Tight(er) Worstcase Bounds on
Dynamic Searching and Priority Queues.
Proc. STOC 2000.

A. Andersson and M. Thorup.
Dynamic String Searching.
Proc. of the twelfth annual ACMSIAM symposium on Discrete algorithms,
SODA 2001.

Arne Andersson, Per Carlsson, and Fredrik Ygge.
Resource Allocation With Noisy Functions.
WAE 2001.
In Algorithm Engineering, LNCS 2141, Springer Verlag 2001.
ISBN 3540425004.

K. Asrat and A. Andersson.
Caching in Multiunit combinatorial auctions.
Proc.
The First International Joint Conference on Autonomous Agents & Multiagent
Systems, AAMAS 2002
.

P. Calrsson, A. Andersson, and F. Ygge.
A Tractable Mechanism for Time Dependent Markets.
2003 IEEE Conference on ECommerce
(CEC'03).

A. Andersson, J. Holmström. M. Willman.
An auction mechanism for polynomialtime execution with combinatorial constraints.
2005 IEEE Conference on ECommerce
(CEC'05).

P. Calrsson, A. Andersson.
A Flexible Model for TreeSructured MultiCommodity Markets
2005 IEEE Conference on ECommerce
(CEC'05).

J. Wilenius, A. Andersson.
Discovering Equilibrium Strategies for a Combinatorial First Price Auction.
IEEE Joint Conference on ECommerce Technology (CEC'07) and Enterprise Computing, ECommerce and EServices (EEE '07).
Workshops

A. Andersson and M. Thorup.
Implementing Monotone Priority Queues.
DIMACS Implementation challenge, 1996.

A. Andersson.
Which flavor of balanced tree?
Plain vanilla!
DIMACS Implementation challenge, 1996.
Invited Talks (in printed proceedings)

A. Andersson.
Sorting and searching revisited.
In Proc. Scandinavian Workshop on Algorithm Theory, 1996.

A. Andersson.
What are the basic principles of sorting and searching?
In Proc. of the Joint ICL/University of Newcastle Seminar, 1996.
Book Chapters

A. Andersson, R. Fagerberg, and K. S. Larsen.
Balanced Binary Search Trees.
In Chapter 10 in Handbook of Data Structures, CRC Press, 2005.

A. Andersson.
Searching and Priority Queues in o(log n) Time.
In Chapter 10 in Handbook of Data Structures, CRC Press, 2005.
Software
Others