Papers authored by Kim S. Larsen

Final versions of most papers can be obtained from the home pages for the various journals and series. Direct links are given for almost all papers below; click on the title to find the abstract and a link to the publisher's version. If you have difficulty obtaining a copy of one of my papers, then please send me an e-mail. References on this page are also available in BibTeX and pdf. You can also use the listing from dblp (book contributions, papers which are to appear, and very recently published papers cannot be found via the dblp listing).

Table of Contents

Peer-Reviewed International Journal Articles
A Technique for Exact Computation of Precoloring Extension on Interval Graphs.
Martin R. Ehmsen and Kim S. Larsen.
International Journal of Foundations of Computer Science, 24(1): 109-122, 2013.

List Factoring and Relative Worst Order Analysis.
Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Algorithmica, 66(2): 287-309, 2013.

A Theoretical Comparison of LRU and LRU-K.
Joan Boyar, Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Acta Informatica, 47(7-8): 359-374, 2010.

Competitive Analysis of the Online Inventory Problem.
Kim S. Larsen and Sanne Wøhlk.
European Journal of Operational Research, 207(2): 685-696, 2010.

Priority Algorithms for Graph Optimization Problems.
Allan Borodin, Joan Boyar, Kim S. Larsen, and Nazanin Mirmohammadi.
Theoretical Computer Science, 411(1): 239-258, 2010.

The Relative Worst Order Ratio Applied to Paging.
Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Journal of Computer and System Sciences, 73(5): 818-843, 2007.

The Maximum Resource Bin Packing Problem.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten M. Pedersen, and Sanne Wøhlk.
Theoretical Computer Science, 362(1-3): 127-139, 2006.

Exponentially Decreasing Number of Operations in Balanced Trees.
Lars Jacobsen and Kim S. Larsen.
Acta Informatica, 82(4): 57-78, 2005.

On-Line Seat Reservations via Off-Line Seating Arrangements.
Jens S. Kohrt and Kim S. Larsen.
International Journal of Foundations of Computer Science, 16(2): 381-397, 2005.

Extending the Accommodating Function.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Acta Informatica, 40(1): 3-35, 2003.

Dynamic TCP Acknowledgment in the LogP Model.
Jens S. Frederiksen, Kim S. Larsen, John Noga, and Patchrawat Uthaisombut.
Journal of Algorithms, 48(2): 407-428, 2003.

Relaxed Multi-Way Trees with Group Updates.
Kim S. Larsen.
Journal of Computer and System Sciences, 66(4): 657-670, 2003.

Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem.
Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin, and Rob van Stee.
Journal of Scheduling, 6(2): 131-147, 2003.

On the Existence and Construction of Non-Extreme (a,b)-Trees.
Lars Jacobsen, Kim S. Larsen, and Morten N. Nielsen.
Information Processing Letters, 84(2): 69-73, 2002.

Fair versus Unrestricted Bin Packing.
Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Algorithmica, 34(2): 181-196, 2002.

Relaxed Red-Black Trees with Group Updates.
Kim S. Larsen.
Acta Informatica, 38(8): 565-586, 2002.

The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Nordic Journal of Computing, 8(4): 463-472, 2001.

Relaxed Balance using Standard Rotations.
Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
Algorithmica, 31(4): 501-512, 2001.

Relaxed Balance for Search Trees with Local Rebalancing.
Kim S. Larsen, Thomas Ottmann, and Eljas Soisalon-Soininen.
Acta Informatica, 37(10): 743-763, 2001.

Variants of (a,b)-Trees with Relaxed Balance.
Lars Jacobsen and Kim S. Larsen.
International Journal of Foundations of Computer Science, 12(4): 455-478, 2001.

The Accommodating Function: a generalization of the competitive ratio.
Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
SIAM Journal on Computing, 31(1): 233-258, 2001.

AVL Trees with Relaxed Balance.
Kim S. Larsen.
Journal of Computer and System Sciences, 61(3): 508-522, 2000.

On Grouping in Relational Algebra.
Kim S. Larsen.
International Journal of Foundations of Computer Science, 10(3): 301-311, 1999.

The Seat Reservation Problem.
Joan Boyar and Kim S. Larsen.
Algorithmica, 25(4): 403-417, 1999.

Partially Persistent Binary Search Trees with Transcript Operations.
Kim S. Larsen.
Discrete Mathematics and Theoretical Computer Science, 3(3): 95-107, 1999.

Sort Order Problems in Relational Databases.
Kim S. Larsen.
International Journal of Foundations of Computer Science, 9(4): 399-429, 1998.

Amortized Constant Relaxed Rebalancing using Standard Rotations.
Kim S. Larsen.
Acta Informatica, 35(10): 859-874, 1998.

Parametric Permutation Routing via Matchings.
Peter Høyer and Kim S. Larsen.
Nordic Journal of Computing, 5(2): 105-114, 1998.

Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy.
Kim S. Larsen.
Information Processing Letters, 65(4): 169-172, 1998.

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
Joan Boyar, Rolf Fagerberg, and Kim S. Larsen.
Journal of Computer and System Sciences, 55(3): 504-521, 1997.

Efficient Rebalancing of B-Trees with Relaxed Balance.
Kim S. Larsen and Rolf Fagerberg.
International Journal of Foundations of Computer Science, 7(2): 169-186, 1996.

Efficient Rebalancing of Chromatic Search Trees.
Joan F. Boyar and Kim S. Larsen.
Journal of Computer and System Sciences, 49(3): 667-682, 1994.

Injectivity of Composite Functions.
Kim S. Larsen and Michael I. Schwartzbach.
Journal of Symbolic Computation, 17(5): 393-408, 1994.

Bounds on Certain Multiplications of Affine Combinations.
Joan Boyar, Faith Fich, and Kim S. Larsen.
Discrete Applied Mathematics, 52(2): 155-167, 1994.

A New Formalism for Relational Algebra.
Kim S. Larsen, Michael I. Schwartzbach, and Erik M. Schmidt.
Information Processing Letters, 41(3): 163-168, 1992.

Peer-Reviewed International Conference Articles
Relative Interval Analysis of Paging Algorithms on Access Graphs.
Joan Boyar, Sushmita Gupta, and Kim S. Larsen.
In Thirteenth Algorithms and Data Structures Symposium, Lecture Notes in Computer Science. Springer. Accepted for publication.

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.
Joan Boyar, Sushmita Gupta, and Kim S. Larsen.
In Thirteenth Scandinavian Symposium and Workshops on Algorithm Theory, volume 7357 of Lecture Notes in Computer Science, pages 328-339. Springer, 2012.

A Comparison of Performance Measures via Online Search.
Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In SIAM Joint FAW-AAIM Conference, volume 7285 of Lecture Notes in Computer Science, pages 303-314. Springer, 2012.

List Factoring and Relative Worst Order Analysis.
Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
In Eighth Workshop on Approximation and Online Algorithms, volume 6534 of Lecture Notes in Computer Science, pages 118-129. Springer, 2011.

Better Bounds on Online Unit Clustering.
Martin R. Ehmsen and Kim S. Larsen.
In Twelfth Scandinavian Symposium and Workshops on Algorithm Theory, volume 6139 of Lecture Notes in Computer Science, pages 371-382. Springer, 2010.

A Comparison of Performance Measures for Online Algorithms.
Joan Boyar, Sandy Irani, and Kim S. Larsen.
In Eleventh International Algorithms and Data Structures Symposium, volume 5664 of Lecture Notes in Computer Science, pages 119-130. Springer, 2009.

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.
Joan Boyar, Martin R. Ehmsen, and Kim S. Larsen.
In Fourth Workshop on Approximation and Online Algorithms, volume 4368 of Lecture Notes in Computer Science, pages 95-107. Springer, 2006.

Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem.
Marco Chiarandini, Thomas Stützle, and Kim S. Larsen.
In Third International Workshop on Hybrid Metaheuristics, volume 4030 of Lecture Notes in Computer Science, pages 162-177. Springer, 2006.

The Maximum Resource Bin Packing Problem.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, and Sanne Wøhlk.
In Fifteenth International Symposium on Fundamentals of Computation Theory, volume 3623 of Lecture Notes in Computer Science, pages 397-408. Springer, 2005.

The Relative Worst Order Ratio Applied to Paging.
Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 718-727. ACM Press, 2005.

Priority Algorithms for Graph Optimization Problems.
Allan Borodin, Joan Boyar, and Kim S. Larsen.
In Second Workshop on Approximation and Online Algorithms, volume 3351 of Lecture Notes in Computer Science, pages 126-139. Springer, 2005.

On-Line Seat Reservations via Off-Line Seating Arrangements.
Jens S. Frederiksen and Kim S. Larsen.
In Eighth International Workshop on Algorithms and Data Structures, volume 2748 of Lecture Notes in Computer Science, pages 174-185. Springer, 2003.

Extending the Accommodating Function.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
In Eighth Annual International Computing and Combinatorics Conference, volume 2387 of Lecture Notes in Computer Science, pages 87-96. Springer, 2002.

Packet Bundling.
Jens S. Frederiksen and Kim S. Larsen.
In Eighth Scandinavian Workshop on Algorithm Theory, volume 2368 of Lecture Notes in Computer Science, pages 328-337. Springer, 2002.

Exponentially Decreasing Number of Operations in Balanced Trees.
Lars Jacobsen and Kim S. Larsen.
In Seventh Italian Conference on Theoretical Computer Science, volume 2202 of Lecture Notes in Computer Science, pages 293-311. Springer, 2001.

Complexity of Layered Binary Search Trees with Relaxed Balance.
Lars Jacobsen and Kim S. Larsen.
In Seventh Italian Conference on Theoretical Computer Science, volume 2202 of Lecture Notes in Computer Science, pages 269-284. Springer, 2001.

Search Trees with Relaxed Balance and Near-Optimal Height.
Rolf Fagerberg, Rune E. Jensen, and Kim S. Larsen.
In Seventh International Workshop on Algorithms and Data Structures, volume 2125 of Lecture Notes in Computer Science, pages 414-425. Springer, 2001.

Relaxed Multi-Way Trees with Group Updates.
Kim S. Larsen.
In Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 93-101. ACM Press, 2001.

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.
Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, and Guo-Hui Lin.
In Sixth Annual International Computing and Combinatorics Conference, volume 1858 of Lecture Notes in Computer Science, pages 221-231. Springer, 2000.

Fair versus Unrestricted Bin Packing.
Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
In Seventh Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 200-213. Springer, 2000.

The Accommodating Function: a generalization of the competitive ratio.
Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
In Sixth International Workshop on Algorithms and Data Structures, volume 1663 of Lecture Notes in Computer Science, pages 74-79. Springer, 1999.

Partially Persistent Binary Search Trees with Transcript Operations.
Kim S. Larsen.
In Fifthteenth Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 350-363. Springer, 1998.

Relaxed Balance for Search Trees with Local Rebalancing.
Kim S. Larsen, Thomas Ottmann, and Eljas Soisalon-Soininen.
In Fifth Annual European Symposium on Algorithms, volume 1284 of Lecture Notes in Computer Science, pages 350-363. Springer, 1997.

Relaxed Balance through Standard Rotations.
Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
In Fifth International Workshop on Algorithms and Data Structures, volume 1272 of Lecture Notes in Computer Science, pages 450-461. Springer, 1997.

Efficient Simplification of Bisimulation Formulas.
Uffe Engberg and Kim S. Larsen.
In Workshop on Tools and Algorithms for the Construction and Analysis of Systems, volume 1019 of Lecture Notes in Computer Science, pages 111-132. Springer, 1995.

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
Joan Boyar, Rolf Fagerberg, and Kim S. Larsen.
In Fourth International Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 270-281. Springer, 1995.

B-Trees with Relaxed Balance.
Kim S. Larsen and Rolf Fagerberg.
In Ninth International Parallel Processing Symposium, pages 196-202. IEEE Computer Society Press, 1995.

AVL Trees with Relaxed Balance.
Kim S. Larsen.
In Eighth International Parallel Processing Symposium, pages 888-893. IEEE Computer Society Press, 1994.

Efficient Rebalancing of Chromatic Search Trees.
Joan F. Boyar and Kim S. Larsen.
In Third Scandinavian Workshop on Algorithm Theory, volume 621 of Lecture Notes in Computer Science, pages 151-164. Springer, 1992.

Fully Abstract Models for a Process Language with Refinement.
Mogens Nielsen, Uffe Engberg, and Kim S. Larsen.
In REX: Linear Time, Branching Time and Partial Order in Logics and Models of Concurrency, volume 354 of Lecture Notes in Computer Science, pages 523-548. Springer, 1989.

Book Contributions
Balanced Binary Search Trees.
Arne Andersson, Rolf Fagerberg, and Kim S. Larsen.
In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer & Information Science Series, pages 10-1-10-28. CRC Press, 2005.

Dictionary of Computer Science, Engineering, and Technology.
Philip A. Laplante, editor.
CRC Press, 2001. One of 58 contributors.

Last modified: Wed May 15 08:23:41 CEST 2013
Kim Skak Larsen (kslarsen@imada.sdu.dk)