Curriculum vitae

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.
• 1983-84: Undergraduate courses in computer science.
• 1990: Ph.D. degree.
• 1994: Appointed to ``docent''.

Senior Academic Positions

• 1990-92: Researcher, Lund University.
• 1992-97: Research assistant, Lund University.
• 1997-98: Associate professor, Lund University.
• 1998-...: Professor, chairholder, Uppsala University.

Leave of absence etc

• 1992-1993 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

Visiting post docs

Teaching and advising

• 1981-82: Teacher (maths and physics) at Söderkullaskolan, Malmö (Junior High School).
• 1982-83: Teacher (maths, physics and chemistry) at Tunaskolan, Lund (Junior High School).
• 1983-84: Teacher (maths, physics, programming and systems science) at Polhemskolan, Lund (Senior High School).
• 1985-98: 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.
• 1991-93: Teaching consultant at SATT-CONTROL, 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 co-advised 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 co-advisor 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

• 1979-80: Member of the education sectional board (``linjenämnden mat-nat''), Lund University.
• 1987-90, 1994-98: Member of the board of the Department of Computer Science and Numerical Analysis, Lund University.
• 1989-90: Member of the Faculty sectional board (``sektionsnämnden, matematik-fysik''), Lund University.
• 1997-98: Chairman of Department of Computer Science and Numerical Analysis, Lund University.
• 1998: Chairman of Computing Science Department, Uppsala University.
• 1999-2000: Chairman of Department of Information Technology, Uppsala University, and chairman od the Computing Science Department (a subdepartment within IT).
• 2002-2003 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;
• 1997-1998: Part-time 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

• 1992-1994: TFR grant ``Efficient Methods for Sorting and Searching''.
• 1994-1997: TFR grant ``Efficient Data Structures-Efficient Software''.
• 1998-2000: TFR grant ``Efficient Data Structures-Efficient Software''.
• 1998-2001: NUTEK grant ``Techniques for Distributed Markets, Negotiation, and Resource Allocation''.
• 2002-2005 Research grant from Sydkraft.
• 2002-2005 Research grant from VR "Algorithms for Advanced Negotiations".

Others

• 1989-- Refereeing for several journals like SIAM Journal of Computing, Acta Informatica, Software--Practice 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.
• 1991-2000: 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 IT--universities, member of program committee form FCT/TCS 2003 and SWAT 2004.

Industrial Experience

Publications

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

• A. Andersson, Ch. Icking, R. Klein, and Th. Ottmann. Binary search trees of almost optimal height.
  Acta Informatica, 28:165-178, 1990.
  
• A. Andersson and S. Carlsson. Construction of a tree from its traversals in optimal time and space.
  Information Processing Letters, 34(1):21-25, 1990.
  
• A. Andersson. A note on the expected behaviour of binary tree traversals.
  Computer Journal, 33(5):471-472, 1990.
  
• A. Andersson. Maintaining alpha-balanced trees by partial rebuilding.
  International Journal of Computer Matehmathics, 38:37-48, 1990.
  
• A. Andersson. A note on searching in a binary search tree.
  Software-Practice and Experience, 21(10):1125-1128, 1991.
  
• A. Andersson. Comments on ``On the balance property of patricia tries: External path length viewpoint''.
  Theoretical Computer Science, 106:391-393, 1992.
  
• A. Andersson and S. Nilsson. Improved behaviour of tries by adaptive branching.
  Information Processing Letters, 46:295-300, 1993.
  
• A. Andersson and S. Nilsson. Efficient implementation of suffix trees.
  Software---Practice and Experience, 25(2):129-141, 1995.
  
• A. Andersson and Th. Ottmann. New tight bounds on uniquely represented dictionaries.
  SIAM Journal of Computing, 24(5):1091-1103, 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 Self-Indexed Sort.
  SIGPLAN Notices , 38(8), 1996.
• A. Andersson and K. Swanson. On the difficulty of range searching.
  Computational Geometry: Theory and Applications , 8(3):115-122, 1997.
  
• A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time?
  Journal of Computer and System Sciences, vol 57, pp 74-93, 1998.
  
• A. Andersson and O. Petersson. Approximate Indexed Lists.
  Journal of Algorithms 29:256-276, 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: 1-28, 1999.
  
• A. Andersson, P.B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions.
  Theoretical Computer Science, vol 215, pp 337-344, 1999.
  
• A. Andersson, N. J. Larsson, and K. Swanson. Suffix trees on words.
  Algorithmica 23, 1999.
  
• A. Andersson, P. Davidsson, and J. Linden, Measure-based performance evaluation.
  Pattern recognition in practice, 1999.
  
• A. Andersson, F. Ygge, Efficient resource alloctaion with non-concave objective functions.
  Computational Optimization and Applications, 20:281-298, 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. 1552-1578, 2001.
• Arne Andersson, Per Carlsson, and Fredrik Ygge. Resource Allocation With Wobbly Functions.
  Computational Optimization and Applications, 23, 2, pp. 171-200, 2002.
• Arne Andersson, Mikkel Thorup. Dynamic Ordered Sets with Exponential Search Trees.
  Journal of the ACM, 2007.
• Maria Karlsson, Fredrik Ygge, and Arne Andersson. Market-Based Approaches to Optimization.
  Computational Intelligence, 2007.
• Per Carlsson, Arne Andersson. A flexible model for tree-structured multi-commodity markets.
  Electronic Commerce Research, vol 7, no 1, March 2007.

• A. Andersson. Optimal bounds on the dictionary problem.
  In Proc. Symposium on Optimal Algorithms, pages 106--114. 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 393--402, 1989.
  
• A. Andersson and T. W. Lai. Fast updating of well-balanced trees.
  In Proc. Scandinavian Workshop on Algorithm Theory, pages 111--121. Springer Verlag, 1990.
  
• A. Andersson and T. W. Lai. Comparison-efficient write-optimal searching and sorting.
  In Proc. 2nd ann. International Symposium on Algorithms, pages 273--282. Springer Verlag, 1991.
  
• A. Andersson and Th. Ottmann. Faster Uniquely Represented Dictionaries.
  In Proc. 32nd IEEE Sympos. Foundations of Computer Science, pages 642--649, 1991.
  
• A. Andersson. Balanced search trees made simple.
  In Proc. Workshop on Algorithms and Data Structures, pages 60--71. 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 317--325. ACM Press, 1994.
  
• A. Andersson and S. Nilsson. Faster searching in tries and quadtrees---an analysis of level compression.
  In Proc. 2nd Annual European Symposium on Algorithms, pages 82-93. 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 714--721. IEEE Computer Society Press, 1994.
  
• A. Andersson and O. Petersson. On-line approximate list indexing with applications.
  In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 20-27, 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 473-481. 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 427--436. 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 417--426. ACM Press, 1995.
  
• A. Andersson. Sublogarithmic searching without multiplications.
  In Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 655--663. 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 large-scale 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 Meta-Level: Model Selection and Data Transformation, pages 54-65, 1998.
  
• Fredrik Ygge, Hans Akkermans, Arne Andersson, Marko Krejic, and Erik Bortjes. The HomeBots System and Field Tests: A Multi-Commodity Market for Predictive Load Management
  Proccedings of the Fourth International Conference and Exhibition on The Practical Application of Intelligent Agents and Multi-Agents (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 (ICMAS-00), 2000.
• A. Andersson and M. Thorup. Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues.
  Proc. STOC 2000.
  
• A. Andersson and M. Thorup. Dynamic String Searching.
  Proc. of the twelfth annual ACM-SIAM 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 3-540-42500-4.
• K. Asrat and A. Andersson. Caching in Multi-unit 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 E-Commerce (CEC'03).
• A. Andersson, J. Holmström. M. Willman. An auction mechanism for polynomial-time execution with combinatorial constraints.
  2005 IEEE Conference on E-Commerce (CEC'05).
• P. Calrsson, A. Andersson. A Flexible Model for Tree-Sructured Multi-Commodity Markets
  2005 IEEE Conference on E-Commerce (CEC'05).
• J. Wilenius, A. Andersson. Discovering Equilibrium Strategies for a Combinatorial First Price Auction.
  IEEE Joint Conference on E-Commerce Technology (CEC'07) and Enterprise Computing, E-Commerce and E-Services (EEE '07).

• 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.

• 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.

• 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.

• A. Andersson. A demonstration of balanced trees.
  Algorithm animation program including user's guide, 1993.
• A. Andersson. Implementing Genral Balanced trees.
  A combined C-implementation and LaTeX file. Compile it! Read it! Run it!
  

• A. Andersson, S. Nilsson and T. Hagerup. Blasting past fusion trees.
  Tech. report, Lund University, 1994.