Publications

Arne Andersson

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

Refereed conferences

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

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

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!

Others

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