Kim S. Larsen

According to our database, Kim S. Larsen authored at least 91 papers between 1988 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Distributed Graph Algorithms with Predictions.

Joan Boyar, Faith Ellen, Kim S. Larsen

CoRR, January, 2025

Brief Announcement: Distributed Graph Algorithms with Predictions.

Joan Boyar, Faith Ellen, Kim S. Larsen

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

Complexity Classes for Online Problems with and Without Predictions.

Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Frontiers of Algorithmics - 19th International Joint Conference, 2025

2024

Online Unit Profit Knapsack with Predictions.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Algorithmica, September, 2024

Advice complexity of adaptive priority algorithms.

Joan Boyar, Kim S. Larsen, Denis Pankratov

Theor. Comput. Sci., February, 2024

On the Online Weighted Non-Crossing Matching Problem.

Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, Denis Pankratov

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

2023

Online Interval Scheduling with Predictions.

Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Online Minimum Spanning Trees with Weight Predictions.

Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Quotable Signatures for Authenticating Shared Quotes.

Joan Boyar, Simon Erfurth, Kim S. Larsen, Ruben Niederhagen

Proceedings of the Progress in Cryptology - LATINCRYPT 2023, 2023

Paging with Succinct Predictions.

Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon

Proceedings of the International Conference on Machine Learning, 2023

2022

Implementing Choreography Extraction.

Luís Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi, Larisa Safina

CoRR, 2022

Online Unit Profit Knapsack with Untrusted Predictions.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

2020

Randomized distributed online algorithms against adaptive offline adversaries.

Joan Boyar, Faith Ellen, Kim S. Larsen

Inf. Process. Lett., 2020

2019

Online Bin Covering with Advice.

Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

2018

The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing.

Joan Boyar, Faith Ellen, Kim S. Larsen

CoRR, 2018

Advice Complexity of Priority Algorithms.

Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Heuristic Variants of A ^* Search for 3D Flight Planning.

Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen

Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2018

Relative Worst-Order Analysis: A Survey.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Formally Proving Size Optimality of Sorting Networks.

Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp

J. Autom. Reason., 2017

Relaxing the Irrevocability Requirement for Online Graph Algorithms.

Joan Boyar, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

How to Get More Out of Your Oracles.

Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp

Proceedings of the Interactive Theorem Proving - 8th International Conference, 2017

The Paths to Choreography Extraction.

Luís Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi

Proceedings of the Foundations of Software Science and Computation Structures, 2017

DNA-Templated Synthesis Optimization.

Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk

Proceedings of the DNA Computing and Molecular Programming - 23rd International Conference, 2017

Constraint Handling in Flight Planning.

Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen

Proceedings of the Principles and Practice of Constraint Programming, 2017

Flight Planning in Free Route Airspaces.

Casper Kehlet Jensen, Marco Chiarandini, Kim S. Larsen

Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, 2017

2016

Online Algorithms with Advice: A Survey.

Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen

SIGACT News, 2016

Batch Coloring of Graphs.

Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

Online Dominating Set.

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Vertical Optimization of Resource Dependent Flight Paths.

Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen

Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

Online Bounded Analysis.

Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Soccer is Harder Than Football.

Jan Christensen, Anders Nicolai Knudsen, Kim S. Larsen

Int. J. Found. Comput. Sci., 2015

2014

Online Multi-Coloring with Advice.

Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Online Bin Packing with Advice.

Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

On the List Update Problem with Advice.

Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz

Proceedings of the Language and Automata Theory and Applications, 2014

2013

A Technique for Exact Computation of precoloring Extension on Interval Graphs.

Martin R. Ehmsen, Kim S. Larsen

Int. J. Found. Comput. Sci., 2013

Online multi-coloring on the path revisited.

Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen

Acta Informatica, 2013

Relative Interval Analysis of Paging Algorithms on Access Graphs.

Joan Boyar, Sushmita Gupta, Kim S. Larsen

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

The Frequent Items Problem in Online Streaming under Various Performance Measures.

Joan Boyar, Kim S. Larsen, Abyayananda Maiti

Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

Online Bin Covering: Expectations vs. Guarantees.

Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Combinatorial Optimization and Applications, 2013

2012

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.

Joan Boyar, Sushmita Gupta, Kim S. Larsen

Proceedings of the Algorithm Theory - SWAT 2012, 2012

A Comparison of Performance Measures via Online Search.

Joan Boyar, Kim S. Larsen, Abyayananda Maiti

Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2012

2010

Priority algorithms for graph optimization problems.

Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi

Theor. Comput. Sci., 2010

Competitive analysis of the online inventory problem.

Kim S. Larsen, Sanne Wøhlk

Eur. J. Oper. Res., 2010

A theoretical comparison of LRU and LRU-K.

Joan Boyar, Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen

Acta Informatica, 2010

List Factoring and Relative Worst Order Analysis.

Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Better Bounds on Online Unit Clustering.

Martin R. Ehmsen, Kim S. Larsen

Proceedings of the Algorithm Theory, 2010

2009

A Comparison of Performance Measures for Online Algorithms.

Joan Boyar, Sandy Irani, Kim S. Larsen

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

2006

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.

Joan Boyar, Martin R. Ehmsen, Kim S. Larsen

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem.

Marco Chiarandini, Thomas Stützle, Kim S. Larsen

Proceedings of the Hybrid Metaheuristics, Third International Workshop, 2006

2005

On-line seat reservations via off-line seating arrangements.

Jens S. Kohrt, Kim S. Larsen

Int. J. Found. Comput. Sci., 2005

The relative worst order ratio applied to paging.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Maximum Resource Bin Packing Problem.

Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, Sanne Wøhlk

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Balanced Binary Search Trees.

Arne Andersson, Rolf Fagerberg, Kim S. Larsen

Proceedings of the Handbook of Data Structures and Applications., 2004

Priority Algorithms for Graph Optimization Problems.

Allan Borodin, Joan Boyar, Kim S. Larsen

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

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, Rob van Stee

J. Sched., 2003

Dynamic TCP acknowledgment in the LogP model.

Jens S. Frederiksen, Kim S. Larsen, John Noga, Patchrawat Uthaisombut

J. Algorithms, 2003

Online Seat Reservations via Offine Seating Arrangements.

Jens S. Frederiksen, Kim S. Larsen

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

2002

On the existence and construction of non-extreme (a, b)-trees.

Lars Jacobsen, Kim S. Larsen, Morten N. Nielsen

Inf. Process. Lett., 2002

Fair versus Unrestricted Bin Packing.

Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen, Leah Epstein

Algorithmica, 2002

Relaxed red-black trees with group updates.

Kim S. Larsen

Acta Informatica, 2002

Packet Bundling.

Jens S. Frederiksen, Kim S. Larsen

Proceedings of the Algorithm Theory, 2002

Extending the Accommodating Function.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen

Nord. J. Comput., 2001

Variants of (A, B)-Trees with Relaxed Balance.

Lars Jacobsen, Kim S. Larsen

Int. J. Found. Comput. Sci., 2001

Relaxed Balance Using Standard Rotations.

Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer

Algorithmica, 2001

Search Trees with Relaxed Balance and Near-Optimal Height.

Rolf Fagerberg, Rune E. Jensen, Kim S. Larsen

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Relaxed Multi-Way Trees with Group Updates.

Kim S. Larsen

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Exponentially Decreasing Number of Operations in Balanced Trees.

Lars Jacobsen, Kim S. Larsen

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

Complexity of Layered Binary Search Trees with Relaxed Balance.

Lars Jacobsen, Kim S. Larsen

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

2000

Fair versus Unrestricted Bin Packing.

Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen

Proceedings of the Algorithm Theory, 2000

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.

Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, Guo-Hui Lin

Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999

On Grouping in Relational Algebra.

Kim S. Larsen

Int. J. Found. Comput. Sci., 1999

The Seat Reservation Problem.

Joan Boyar, Kim S. Larsen

Algorithmica, 1999

The Accommodating Function - A Generalization of the Competitive Ratio.

Joan Boyar, Kim S. Larsen, Morten N. Nielsen

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

1998

Parametric Permutation Routing via Matchings.

Peter Høyer, Kim S. Larsen

Nord. J. Comput., 1998

Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy.

Kim S. Larsen

Inf. Process. Lett., 1998

Sort Order Problems in Relational Databases.

Kim S. Larsen

Int. J. Found. Comput. Sci., 1998

Amortized Constant Relaxed Rebalancing Using Standard Rotations.

Kim S. Larsen

Acta Informatica, 1998

Partially Persistent Search Trees with Transcript Operations.

Kim S. Larsen

Proceedings of the STACS 98, 1998

1997

Relaxed Balance through Standard Rotations.

Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Relaxed Balance for Search Trees with Local Rebalancing.

Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen

Proceedings of the Algorithms, 1997

1996

Efficient Rebalancing of B-Trees with Relaxed Balance.

Kim S. Larsen, Rolf Fagerberg

Int. J. Found. Comput. Sci., 1996

1995

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.

Joan Boyar, Rolf Fagerberg, Kim S. Larsen

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Efficient Simplification of Bisimulation Formulas.

Uffe Engberg, Kim S. Larsen

Proceedings of the Tools and Algorithms for Construction and Analysis of Systems, 1995

B-trees with relaxed balance.

Kim S. Larsen, Rolf Fagerberg

Proceedings of IPPS '95, 1995

1994

Injectivity of Composite Functions.

Kim S. Larsen, Michael I. Schwartzbach

J. Symb. Comput., 1994

Bounds on Certain Multiplications of Affine Combinations.

Joan Boyar, Faith E. Fich, Kim S. Larsen

Discret. Appl. Math., 1994

AVL Trees with Relaxed Balance.

Kim S. Larsen

Proceedings of the 8th International Symposium on Parallel Processing, 1994

1992

A New Formalism for Relational Algebra.

Kim S. Larsen, Michael I. Schwartzbach, Erik Meineche Schmidt

Inf. Process. Lett., 1992

Efficient Rebalancing of Chromatic Search Trees.

Joan Boyar, Kim S. Larsen

Proceedings of the Algorithm Theory, 1992

1988

Fully abstract models for a process language with refinement.

Mogens Nielsen, Uffe Engberg, Kim S. Larsen

Proceedings of the Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, Noordwijkerhout, The Netherlands, May 30, 1988