News Connections For Students Contact

Publications

Bibliometric Overview

Journal Venue Analysis: According to the Danish Bibliometric Research Indicator, the best 20% of venues are categorized as "Level 2". As indicated, we publish a far larger percentage in the top venues. For each venue, the ministry's latest bibliometric category is used. Conference publications are not included.

Publication List

We list publications by members of the group independent of the exact area for the work. For each year, journal articles are listed before conference papers, and in each category, papers are listed alphabetically by authors' last names.

Acknowledgement: We are grateful to dblp (2018-12-07) for providing data for the publication list.


2018

Batch Coloring of Graphs.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
Algorithmica 80(11): 3293-3315, 2018.

Online-bounded analysis.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
J. Scheduling 21(4): 429-441, 2018.

Weighted Online Problems with Advice.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
Theory Comput. Syst. 62(6): 1443-1469, 2018.

Multiplicative complexity of vector valued Boolean functions.
Joan Boyar, Magnus Gausdal Find.
Theor. Comput. Sci. 720: 36-46, 2018.

Adding isolated vertices makes some greedy online algorithms optimal.
Joan Boyar, Christian Kudahl.
Discrete Applied Mathematics 246: 12-21, 2018.

Online edge coloring of paths and trees with a fixed number of colors.
Lene M. Favrholdt, Jesper W. Mikkelsen.
Acta Inf. 55(1): 57-80, 2018.

DNA-templated synthesis optimization.
Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
Natural Computing 17(4): 693-707, 2018.

Advice Complexity of Priority Algorithms.
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov.
WAOA, Lecture Notes in Computer Science 11312: 69-86, Springer, 2018.
[Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers.]

Relative Worst-Order Analysis: A Survey.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
Adventures Between Lower Bounds and Higher Altitudes, Lecture Notes in Computer Science 11011: 216-230, Springer, 2018.
[Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday.]

Heuristic Variants of A* Search for 3D Flight Planning.
Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
CPAIOR, Lecture Notes in Computer Science 10848: 361-376, Springer, 2018.
[Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings.]


2017

Online Algorithms with Advice: A Survey.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen.
ACM Comput. Surv. 50(2): 19:1-19:34, 2017.

The Advice Complexity of a Class of Hard Online Problems.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
Theory Comput. Syst. 61(4): 1128-1177, 2017.

On the list update problem with advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
Inf. Comput. 253: 411-423, 2017.

Formally Proving Size Optimality of Sorting Networks.
Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
J. Autom. Reasoning 59(4): 425-454, 2017.

Relaxing the Irrevocability Requirement for Online Graph Algorithms.
Joan Boyar, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 10389: 217-228, Springer, 2017.
[Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL, Canada, July 31 - August 2, 2017, Proceedings.]

The Paths to Choreography Extraction.
Luís Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi.
FoSSaCS, Lecture Notes in Computer Science 10203: 424-440, 2017.
[Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings.]

How to Get More Out of Your Oracles.
Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
ITP, Lecture Notes in Computer Science 10499: 164-170, Springer, 2017.
[Interactive Theorem Proving - 8th International Conference, ITP 2017, Brasília, Brazil, September 26-29, 2017, Proceedings.]

DNA-Templated Synthesis Optimization.
Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
DNA, Lecture Notes in Computer Science 10467: 17-32, Springer, 2017.
[DNA Computing and Molecular Programming - 23rd International Conference, DNA 23, Austin, TX, USA, September 24-28, 2017, Proceedings.]

Flight Planning in Free Route Airspaces.
Casper Kehlet Jensen, Marco Chiarandini, Kim S. Larsen.
ATMOS, OASICS 59: 14:1-14:14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
[17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2017, September 7-8, 2017, Vienna, Austria.]

Constraint Handling in Flight Planning.
Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
CP, Lecture Notes in Computer Science 10416: 354-369, Springer, 2017.
[Principles and Practice of Constraint Programming - 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings.]


2016

Online Algorithms with Advice: A Survey.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen.
SIGACT News 47(3): 93-129, 2016.

On various nonlinearity measures for boolean functions.
Joan Boyar, Magnus Gausdal Find, René Peralta.
Cryptography and Communications 8(3): 313-330, 2016.

Online Bin Packing with Advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
Algorithmica 74(1): 507-527, 2016.

Online Dominating Set.
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
SWAT, LIPIcs 53: 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
[15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, 2016, Reykjavik, Iceland.]

Online Bounded Analysis.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
CSR, Lecture Notes in Computer Science 9691: 131-145, Springer, 2016.
[Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings.]

Batch Coloring of Graphs.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
WAOA, Lecture Notes in Computer Science 10138: 52-64, Springer, 2016.
[Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers.]

Weighted Online Problems with Advice.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
IWOCA, Lecture Notes in Computer Science 9843: 179-190, Springer, 2016.
[Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings.]

Vertical Optimization of Resource Dependent Flight Paths.
Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
ECAI, Frontiers in Artificial Intelligence and Applications 285: 639-645, IOS Press, 2016.
[ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016).]


2015

Cancellation-free circuits in unbounded and bounded depth.
Joan Boyar, Magnus Gausdal Find.
Theor. Comput. Sci. 590: 17-26, 2015.

Relative interval analysis of paging algorithms on access graphs.
Joan Boyar, Sushmita Gupta, Kim S. Larsen.
Theor. Comput. Sci. 568: 28-48, 2015.

A Comparison of Performance Measures for Online Algorithms.
Joan Boyar, Sandy Irani, Kim S. Larsen.
Algorithmica 72(4): 969-994, 2015.

The Frequent Items Problem in Online Streaming Under Various Performance Measures.
Joan Boyar, Kim S. Larsen, Abyayananda Maiti.
Int. J. Found. Comput. Sci. 26(4): 413-440, 2015.

Online multi-coloring with advice.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
Theor. Comput. Sci. 596: 79-91, 2015.

Soccer is Harder Than Football.
Jan Christensen, Anders Nicolai Knudsen, Kim S. Larsen.
Int. J. Found. Comput. Sci. 26(4): 477-486, 2015.

Advice Complexity for a Class of Online Problems.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
STACS, LIPIcs 30: 116-129, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany.]

Constructive Relationships Between Algebraic Thickness and Normality.
Joan Boyar, Magnus Gausdal Find.
FCT, Lecture Notes in Computer Science 9210: 106-117, Springer, 2015.
[Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings.]

Adding Isolated Vertices Makes Some Online Algorithms Optimal.
Joan Boyar, Christian Kudahl.
IWOCA, Lecture Notes in Computer Science 9538: 65-76, Springer, 2015.
[Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers.]


2014

A comparison of performance measures via online search.
Joan Boyar, Kim S. Larsen, Abyayananda Maiti.
Theor. Comput. Sci. 532: 2-13, 2014.

Online bin covering: Expectations vs. guarantees.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
Theor. Comput. Sci. 556: 71-84, 2014.

The Relationship between Multiplicative Complexity and Nonlinearity.
Joan Boyar, Magnus Gausdal Find.
MFCS (2), Lecture Notes in Computer Science 8635: 130-140, Springer, 2014.
[Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II.]

On the List Update Problem with Advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
LATA, Lecture Notes in Computer Science 8370: 210-221, Springer, 2014.
[Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings.]

Online Bin Packing with Advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
STACS, LIPIcs 25: 174-186, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014.
[31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France.]

Online Multi-Coloring with Advice.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
WAOA, Lecture Notes in Computer Science 8952: 83-94, Springer, 2014.
[Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers.]

Online Dual Edge Coloring of Paths and Trees.
Lene M. Favrholdt, Jesper W. Mikkelsen.
WAOA, Lecture Notes in Computer Science 8952: 181-192, Springer, 2014.
[Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers.]


2013

Logic Minimization Techniques with Applications to Cryptology.
Joan Boyar, Philip Matthews, René Peralta.
J. Cryptology 26(2): 280-312, 2013.

Online multi-coloring on the path revisited.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
Acta Inf. 50(5-6): 343-357, 2013.

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

A Technique for Exact Computation of precoloring Extension on Interval Graphs.
Martin R. Ehmsen, Kim S. Larsen.
Int. J. Found. Comput. Sci. 24(1): 109-122, 2013.

Better bounds on online unit clustering.
Martin R. Ehmsen, Kim S. Larsen.
Theor. Comput. Sci. 500: 1-24, 2013.

Bounds for Scheduling Jobs on Grid Processors.
Joan Boyar, Faith Ellen.
Space-Efficient Data Structures, Streams, and Algorithms, Lecture Notes in Computer Science 8066: 12-26, Springer, 2013.
[Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday.]

Four Measures of Nonlinearity.
Joan Boyar, Magnus Find, René Peralta.
CIAC, Lecture Notes in Computer Science 7878: 61-72, Springer, 2013.
[Algorithms and Complexity, 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings.]

Cancellation-Free Circuits in Unbounded and Bounded Depth.
Joan Boyar, Magnus Gausdal Find.
FCT, Lecture Notes in Computer Science 8070: 159-170, Springer, 2013.
[Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings.]

Relative Interval Analysis of Paging Algorithms on Access Graphs.
Joan Boyar, Sushmita Gupta, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 8037: 195-206, Springer, 2013.
[Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings.]

The Frequent Items Problem in Online Streaming under Various Performance Measures.
Joan Boyar, Kim S. Larsen, Abyayananda Maiti.
FCT, Lecture Notes in Computer Science 8070: 60-71, Springer, 2013.
[Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings.]

Online Bin Covering: Expectations vs. Guarantees.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
COCOA, Lecture Notes in Computer Science 8287: 226-237, Springer, 2013.
[Combinatorial Optimization and Applications - 7th International Conference, COCOA 2013, Chengdu, China, December 12-14, 2013, Proceedings.]


2012

On the absolute approximation ratio for First Fit and related results.
Joan Boyar, György Dósa, Leah Epstein.
Discrete Applied Mathematics 160(13-14): 1914-1923, 2012.

A new variable-sized bin packing problem.
Joan Boyar, Lene M. Favrholdt.
J. Scheduling 15(3): 273-287, 2012.

Comparing online algorithms for bin packing problems.
Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt.
J. Scheduling 15(1): 13-21, 2012.

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.
Joan Boyar, Sushmita Gupta, Kim S. Larsen.
SWAT, Lecture Notes in Computer Science 7357: 328-339, Springer, 2012.
[Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings.]

A Comparison of Performance Measures via Online Search.
Joan Boyar, Kim S. Larsen, Abyayananda Maiti.
FAW-AAIM, Lecture Notes in Computer Science 7285: 303-314, Springer, 2012.
[Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Beijing, China, May 14-16, 2012. Proceedings.]

A Small Depth-16 Circuit for the AES S-Box.
Joan Boyar, René Peralta.
SEC, IFIP Advances in Information and Communication Technology 376: 287-298, Springer, 2012.
[Information Security and Privacy Research - 27th IFIP TC 11 Information Security and Privacy Conference, SEC 2012, Heraklion, Crete, Greece, June 4-6, 2012. Proceedings.]


2011

Online variable-sized bin packing with conflicts.
Leah Epstein, Lene M. Favrholdt, Asaf Levin.
Discrete Optimization 8(2): 333-343, 2011.


2010

Priority algorithms for graph optimization problems.
Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi.
Theor. Comput. Sci. 411(1): 239-258, 2010.

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

Tight results for Next Fit and Worst Fit with resource augmentation.
Joan Boyar, Leah Epstein, Asaf Levin.
Theor. Comput. Sci. 411(26-28): 2572-2580, 2010.

Scheduling Jobs on Grid Processors.
Joan Boyar, Lene M. Favrholdt.
Algorithmica 57(4): 819-847, 2010.

Comparing First-Fit and Next-Fit for online edge coloring.
Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai.
Theor. Comput. Sci. 411(16-18): 1734-1741, 2010.

Competitive analysis of the online inventory problem.
Kim S. Larsen, Sanne Wøhlk.
European Journal of Operational Research 207(2): 685-696, 2010.

A New Combinational Logic Minimization Technique with Applications to Cryptology.
Joan Boyar, René Peralta.
SEA, Lecture Notes in Computer Science 6049: 178-189, Springer, 2010.
[Experimental Algorithms, 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings.]

List Factoring and Relative Worst Order Analysis.
Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen.
WAOA, Lecture Notes in Computer Science 6534: 118-129, Springer, 2010.
[Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010. Revised Papers.]

Better Bounds on Online Unit Clustering.
Martin R. Ehmsen, Kim S. Larsen.
SWAT, Lecture Notes in Computer Science 6139: 371-382, Springer, 2010.
[Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings.]


2009

A Comparison of Performance Measures for Online Algorithms.
Joan Boyar, Sandy Irani, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 5664: 119-130, Springer, 2009.
[Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings.]


2008

The relative worst order ratio applied to seat reservation.
Joan Boyar, Paul Medvedev.
ACM Trans. Algorithms 4(4): 48:1-48:22, 2008.

Tight bounds for the multiplicative complexity of symmetric functions.
Joan Boyar, René Peralta.
Theor. Comput. Sci. 396(1-3): 223-246, 2008.

On the Shortest Linear Straight-Line Program for Computing Linear Forms.
Joan Boyar, Philip Matthews, René Peralta.
MFCS, Lecture Notes in Computer Science 5162: 168-179, Springer, 2008.
[Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings.]

Comparing First-Fit and Next-Fit for Online Edge Coloring.
Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai.
ISAAC, Lecture Notes in Computer Science 5369: 89-99, Springer, 2008.
[Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings.]


2007

The relative worst order ratio for online algorithms.
Joan Boyar, Lene M. Favrholdt.
ACM Trans. Algorithms 3(2): 22, 2007.

The relative worst-order ratio applied to paging.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
J. Comput. Syst. Sci. 73(5): 818-843, 2007.


2006

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.
Theor. Comput. Sci. 362(1-3): 127-139, 2006.

Separating online scheduling algorithms with the relative worst order ratio.
Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt.
J. Comb. Optim. 12(4): 363-386, 2006.

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.
Joan Boyar, Martin R. Ehmsen, Kim S. Larsen.
WAOA, Lecture Notes in Computer Science 4368: 95-107, Springer, 2006.
[Approximation and Online Algorithms, 4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers.]

Scheduling Jobs on Grid Processors.
Joan Boyar, Lene M. Favrholdt.
SWAT, Lecture Notes in Computer Science 4059: 17-28, Springer, 2006.
[Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings.]

Concrete Multiplicative Complexity of Symmetric Functions.
Joan Boyar, René Peralta.
MFCS, Lecture Notes in Computer Science 4162: 179-189, Springer, 2006.
[Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings.]

Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem.
Marco Chiarandini, Thomas Stützle, Kim S. Larsen.
Hybrid Metaheuristics, Lecture Notes in Computer Science 4030: 162-177, Springer, 2006.
[Hybrid Metaheuristics, Third International Workshop, HM 2006, Gran Canaria, Spain, October 13-15, 2006, Proceedings.]


2005

On paging with locality of reference.
Susanne Albers, Lene M. Favrholdt, Oliver Giel.
J. Comput. Syst. Sci. 70(2): 145-175, 2005.

The Exact Multiplicative Complexity of the Hamming Weight Function
Joan Boyar, René Peralta.
Electronic Colloquium on Computational Complexity (ECCC)(049), 2005.

Optimal non-preemptive semi-online scheduling on two related machines.
Leah Epstein, Lene M. Favrholdt.
J. Algorithms 57(1): 49-73, 2005.

Exponentially decreasing number of operations in balanced trees.
Lars Jacobsen, Kim S. Larsen.
Acta Inf. 42(1): 57-78, 2005.

On-line seat reservations via off-line seating arrangements.
Jens S. Kohrt, Kim S. Larsen.
Int. J. Found. Comput. Sci. 16(2): 381-397, 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.
FCT, Lecture Notes in Computer Science 3623: 397-408, Springer, 2005.
[Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings.]

The relative worst order ratio applied to paging.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
SODA: 718-727, SIAM, 2005.
[Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005.]


2004

Seat reservation allowing seat changes.
Joan Boyar, Susan Krarup, Morten N. Nielsen.
J. Algorithms 52(2): 169-192, 2004.

Priority Algorithms for Graph Optimization Problems.
Allan Borodin, Joan Boyar, Kim S. Larsen.
WAOA, Lecture Notes in Computer Science 3351: 126-139, Springer, 2004.
[Approximation and Online Algorithms, Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers.]

The Relative Worst Order Ratio Applied to Seat Reservation.
Joan Boyar, Paul Medvedev.
SWAT, Lecture Notes in Computer Science 3111: 90-101, Springer, 2004.
[Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings.]

Balanced Binary Search Trees.
Arne Andersson, Rolf Fagerberg, Kim S. Larsen.
Handbook of Data Structures and Applications, 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. Scheduling 6(2): 131-147, 2003.

Extending the accommodating function.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen.
Acta Inf. 40(1): 3-35, 2003.

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins.
Leah Epstein, Lene M. Favrholdt.
Acta Cybern. 16(1): 57-66, 2003.

On-Line Edge-Coloring with a Fixed Number of Colors.
Lene M. Favrholdt, Morten N. Nielsen.
Algorithmica 35(2): 176-191, 2003.

Dynamic TCP acknowledgment in the LogP model.
Jens S. Frederiksen, Kim S. Larsen, John Noga, Patchrawat Uthaisombut.
J. Algorithms 48(2): 407-428, 2003.

Relaxed multi-way trees with group updates.
Kim S. Larsen.
J. Comput. Syst. Sci. 66(4): 657-670, 2003.

The Relative Worst Order Ratio for On-Line Algorithms.
Joan Boyar, Lene M. Favrholdt.
CIAC, Lecture Notes in Computer Science 2653: 58-69, Springer, 2003.
[Algorithms and Complexity, 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings.]

Online Seat Reservations via Offine Seating Arrangements.
Jens S. Frederiksen, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 2748: 174-185, Springer, 2003.
[Algorithms and Data Structures, 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 - August 1, 2003, Proceedings.]


2002

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

Optimal preemptive semi-online scheduling to minimize makespan on two related machines.
Leah Epstein, Lene M. Favrholdt.
Oper. Res. Lett. 30(4): 269-275, 2002.

On the existence and construction of non-extreme (a, b)-trees.
Lars Jacobsen, Kim S. Larsen, Morten N. Nielsen.
Inf. Process. Lett. 84(2): 69-73, 2002.

Relaxed red-black trees with group updates.
Kim S. Larsen.
Acta Inf. 38(8): 565-586, 2002.

On paging with locality of reference.
Susanne Albers, Lene M. Favrholdt, Oliver Giel.
STOC: 258-267, ACM, 2002.
[Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada.]

Extending the Accommodating Function.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen.
COCOON, Lecture Notes in Computer Science 2387: 87-96, Springer, 2002.
[Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings.]

Optimal Non-preemptive Semi-online Scheduling on Two Related Machines.
Leah Epstein, Lene M. Favrholdt.
MFCS, Lecture Notes in Computer Science 2420: 245-256, Springer, 2002.
[Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings.]

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins.
Leah Epstein, Lene M. Favrholdt.
COCOON, Lecture Notes in Computer Science 2387: 467-475, Springer, 2002.
[Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings.]

Packet Bundling.
Jens S. Frederiksen, Kim S. Larsen.
SWAT, Lecture Notes in Computer Science 2368: 328-337, Springer, 2002.
[Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings.]


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. 8(4): 463-472, 2001.

Seat Reservation Allowing Seat Changes.
Joan Boyar, Susan Krarup, Morten N. Nielsen.
Electr. Notes Theor. Comput. Sci. 50(1): 24-38, 2001.

The Accommodating Function: A Generalization of the Competitive Ratio.
Joan Boyar, Kim S. Larsen, Morten N. Nielsen.
SIAM J. Comput. 31(1): 233-258, 2001.

Variants of (A, B)-Trees with Relaxed Balance.
Lars Jacobsen, Kim S. Larsen.
Int. J. Found. Comput. Sci. 12(4): 455-478, 2001.

Relaxed balance for search trees with local rebalancing.
Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen.
Acta Inf. 37(10): 743-763, 2001.

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

Search Trees with Relaxed Balance and Near-Optimal Height.
Rolf Fagerberg, Rune E. Jensen, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 2125: 414-425, Springer, 2001.
[Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings.]

Complexity of Layered Binary Search Trees with Relaxed Balance.
Lars Jacobsen, Kim S. Larsen.
ICTCS, Lecture Notes in Computer Science 2202: 269-284, Springer, 2001.
[Theoretical Computer Science, 7th Italian Conference, ICTCS 2001, Torino, Italy, October 4-6, 2001, Proceedings.]

Exponentially Decreasing Number of Operations in Balanced Trees.
Lars Jacobsen, Kim S. Larsen.
ICTCS, Lecture Notes in Computer Science 2202: 293-311, Springer, 2001.
[Theoretical Computer Science, 7th Italian Conference, ICTCS 2001, Torino, Italy, October 4-6, 2001, Proceedings.]

Relaxed Multi-Way Trees with Group Updates.
Kim S. Larsen.
PODS, ACM, 2001.
[Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California, USA.]


2000

Short Non-Interactive Cryptographic Proofs.
Joan Boyar, Ivan Damgård, René Peralta.
J. Cryptology 13(4): 449-472, 2000.

On the multiplicative complexity of Boolean functions over the basis (cap, +, 1).
Joan Boyar, René Peralta, Denis Pochuev.
Theor. Comput. Sci. 235(1): 43-57, 2000.

AVL Trees with Relaxed Balance.
Kim S. Larsen.
J. Comput. Syst. Sci. 61(3): 508-522, 2000.

Fair versus Unrestricted Bin Packing.
Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen.
SWAT, Lecture Notes in Computer Science 1851: 200-213, Springer, 2000.
[Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings.]

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.
Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, Guo-Hui Lin.
COCOON, Lecture Notes in Computer Science 1858: 221-231, Springer, 2000.
[Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26-28, 2000, Proceedings.]

On-Line Edge-Coloring with a Fixed Number of Colors.
Lene M. Favrholdt, Morten N. Nielsen.
FSTTCS, Lecture Notes in Computer Science 1974: 106-116, Springer, 2000.
[Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS 2000 New Delhi, India, December 13-15, 2000, Proceedings..]


1999

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

Partially persistent search trees with transcript operations.
Kim S. Larsen.
Discrete Mathematics & Theoretical Computer Science 3(3): 95-107, 1999.

On Grouping in Relational Algebra.
Kim S. Larsen.
Int. J. Found. Comput. Sci. 10(3): 301-311, 1999.

The Accommodating Function - A Generalization of the Competitive Ratio.
Joan Boyar, Kim S. Larsen, Morten N. Nielsen.
WADS, Lecture Notes in Computer Science 1663: 74-79, Springer, 1999.
[Algorithms and Data Structures, 6th International Workshop, WADS '99, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings.]


1998

Parametric Permutation Routing via Matchings.
Peter Høyer, Kim S. Larsen.
Nord. J. Comput. 5(2): 105-114, 1998.

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

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

Sort Order Problems in Relational Databases.
Kim S. Larsen.
Int. J. Found. Comput. Sci. 9(4): 399-430, 1998.

Partially Persistent Search Trees with Transcript Operations.
Kim S. Larsen.
STACS, Lecture Notes in Computer Science 1373: 309-319, Springer, 1998.
[STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings.]


1997

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
Joan Boyar, Rolf Fagerberg, Kim S. Larsen.
J. Comput. Syst. Sci. 55(3): 504-521, 1997.

Relaxed Balance for Search Trees with Local Rebalancing.
Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen.
ESA, Lecture Notes in Computer Science 1284: 350-363, Springer, 1997.
[Algorithms - ESA '97, 5th Annual European Symposium, Graz, Austria, September 15-17, 1997, Proceedings.]

Relaxed Balance through Standard Rotations.
Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer.
WADS, Lecture Notes in Computer Science 1272: 450-461, Springer, 1997.
[Algorithms and Data Structures, 5th International Workshop, WADS '97, Halifax, Nova Scotia, Canada, August 6-8, 1997, Proceedings.]


1996

Efficient Rebalancing of B-Trees with Relaxed Balance.
Kim S. Larsen, Rolf Fagerberg.
Int. J. Found. Comput. Sci. 7(2): 169-186, 1996.

Short Discrete Proofs.
Joan Boyar, René Peralta.
EUROCRYPT, Lecture Notes in Computer Science 1070: 131-142, Springer, 1996.
[Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding.]


1995

Subquadratic Zero-Knowledge.
Joan Boyar, Gilles Brassard, René Peralta.
J. ACM 42(6): 1169-1193, 1995.

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
Joan Boyar, Rolf Fagerberg, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 955: 270-281, Springer, 1995.
[Algorithms and Data Structures, 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings.]

Efficient Simplification of Bisimulation Formulas.
Uffe Engberg, Kim S. Larsen.
TACAS, Lecture Notes in Computer Science 1019: 111-132, Springer, 1995.
[Tools and Algorithms for Construction and Analysis of Systems, First International Workshop, TACAS '95, Aarhus, Denmark, May 19-20, 1995, Proceedings.]

B-trees with relaxed balance.
Kim S. Larsen, Rolf Fagerberg.
IPPS: 196-202, IEEE Computer Society, 1995.
[Proceedings of IPPS '95, The 9th International Parallel Processing Symposium, April 25-28, 1995, Santa Barbara, California, USA.]


1994

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

Efficient Rebalancing of Chromatic Search Trees.
Joan Boyar, Kim S. Larsen.
J. Comput. Syst. Sci. 49(3): 667-682, 1994.

Injectivity of Composite Functions.
Kim S. Larsen, Michael I. Schwartzbach.
J. Symb. Comput. 17(5): 393-408, 1994.

AVL Trees with Relaxed Balance.
Kim S. Larsen.
IPPS: 888-893, IEEE Computer Society, 1994.
[Proceedings of the 8th International Symposium on Parallel Processing, Cancún, Mexico, April 1994.]


1993

On the Communication Complexity of Zero-Knowledge Proofs.
Joan Boyar, Carsten Lund, René Peralta.
J. Cryptology 6(2): 65-85, 1993.


1992

An Arithmetic Model of Computation Equivalent to Threshold Circuits.
Joan Boyar, Gudmund Skovbjerg Frandsen, Carl Sturtivant.
Theor. Comput. Sci. 93(2): 303-319, 1992.

A New Formalism for Relational Algebra.
Kim S. Larsen, Michael I. Schwartzbach, Erik Meineche Schmidt.
Inf. Process. Lett. 41(3): 163-168, 1992.

Efficient Rebalancing of Chromatic Search Trees.
Joan Boyar, Kim S. Larsen.
SWAT, Lecture Notes in Computer Science 621: 151-164, Springer, 1992.
[Algorithm Theory - SWAT '92, Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8-10, 1992, Proceedings.]


1991

Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies.
Joan Boyar, Katalin Friedl, Carsten Lund.
J. Cryptology 4(3): 185-206, 1991.

Subquadratic Zero-Knowledge
Joan Boyar, Gilles Brassard, René Peralta.
FOCS: 69-78, IEEE Computer Society, 1991.
[32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991.]


1990

A Discrete Logarithm Implementation of Perfect Zero-Knowledge Blobs.
Joan Boyar, S. A. Kurtz, Mark W. Krentel.
J. Cryptology 2(2): 63-76, 1990.

Convertible Undeniable Signatures.
Joan Boyar, David Chaum, Ivan Damgård, Torben P. Pedersen.
CRYPTO, Lecture Notes in Computer Science 537: 189-205, Springer, 1990.
[Advances in Cryptology - CRYPTO '90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings.]


1989

Inferring Sequences Produced by a Linear Congruential Generator Missing Low-Order Bits.
Joan Boyar.
J. Cryptology 1(3): 177-184, 1989.

Inferring sequences produced by pseudo-random number generators.
Joan Boyar.
J. ACM 36(1): 129-141, 1989.

Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies.
Joan Boyar, Katalin Friedl, Carsten Lund.
EUROCRYPT, Lecture Notes in Computer Science 434: 155-172, Springer, 1989.
[Advances in Cryptology - EUROCRYPT '89, Workshop on the Theory and Application of of Cryptographic Techniques, Houthalen, Belgium, April 10-13, 1989, Proceedings.]

On the Concrete Complexity of Zero-Knowledge Proofs.
Joan Boyar, René Peralta.
CRYPTO, Lecture Notes in Computer Science 435: 507-525, Springer, 1989.
[Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings.]


1988

Fully abstract models for a process language with refinement.
Mogens Nielsen, Uffe Engberg, Kim S. Larsen.
REX Workshop, Lecture Notes in Computer Science 354: 523-548, Springer, 1988.
[Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, Noordwijkerhout, The Netherlands, May 30 - June 3, 1988, Proceedings.]


1987

Coloring Planar Graphs in Parallel.
Joan Boyar, Howard J. Karloff.
J. Algorithms 8(4): 470-479, 1987.


1982

Inferring a Sequence Generated by a Linear Congruence
Joan B. Plumstead.
FOCS: 153-159, IEEE Computer Society, 1982.
[23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982.]