(Logo)  

   

Publications

Online Bin Covering with Advice
Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen
To appear in Algorithmica
Preliminary version in 16th WADS, LNCS 11646: 225-238, 2019

Relative Worst-Order Analysis: A Survey
Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen
ACM Computing Surveys 54(1):1-21, Article No. 8, 2020
Preliminary version in: In Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovic on the Occasion of His 60th Birthday, LNCS 11011: 216-230, 2018

Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen
Algorithmica 81(5):1938-1964, 2019
Preliminary version in 15th SWAT, LIPIcs 53: 21:1-21:15, 2016

Online Dual Edge Coloring of Paths and Trees
Lene M. Favrholdt and Jesper W. Mikkelsen
Acta Informatica 55(1): 57-80, 2018
Preliminary version in 12th WAOA, LNCS 8952: 181-192, 2014

Batch Coloring of Graphs
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin
Algorithmica 80(11): 3293-3315, 2018
14th Workshop on Approximation and Online Algorithms, LNCS 10138: 52-64, 2016

Weighted online problems with advice
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen
Theory of Computing Systems 62(6), 1443-1469, 2018
Preliminary version in 27th IWOCA, LNCS 9843: 179-190, 2016

Online-Bounded Analysis
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Journal of Scheduling 21(4): 429-441, 2018
Preliminary version in 11th CSR, LNCS 9691: 131-145, 2016

Relaxing the Irrevocability Requirement for Online Graph Algorithms
Joan Boyar, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen
15th International Algorithms and Data Structures Symposium (WADS), LNCS 10389: 217-228, 2017

Online Algorithms with Advice: A Survey
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen
ACM Computing Surveys 50(2):1-34, 2017. Article No. 19.
Preliminary version in ACM SIGACT News, 47(3): 93-129, 2016

Advice Complexity for a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen
Theory of Computing Systems 61(4): 1128-1177, 2017
Preliminary version in 32nd STACS, LIPIcs 30: 116-129, 2015

Online Multi-Coloring with Advice
Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen
Theoretical Computer Science 596: 79-91, 2015.
Preliminary version in the 12th WAOA, LNCS 8952: 83-94, 2014

Online Bin Covering: Expectations vs. Guarantees
Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen
Theoretical Computer Science 556: 71-84, 2014.
Preliminary version in the 7th COCOA, LNCS 8287: 226-237, 2013

Online Multi-Coloring on the Path Revisited
Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen
Acta Informatica 50(5-6): 343-357, 2013

Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture
Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M. Favrholdt
Wiley 2012

A New Variable-Sized Bin Packing Problem
Joan Boyar and Lene M. Favrholdt
Journal of Scheduling 15(3): 273-287, 2012
DOI: 10.1007/s10951-010-0199-4

CATCHprofiles: Clustering and Alignment Tool for ChIP Profiles
Fiona G. G. Nielsen, Kasper G. Markus, Rune M. Friborg, Lene M. Favrholdt, Hendrik G. Stunnenberg, and Martijn Huynen
PLoS ONE 7(1), 2012
DOI:10.1371/journal.pone.0028272

Comparing Online Algorithms for Bin Packing Problems
Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt
Journal of Scheduling 15(1): 13-21, 2012
DOI:10.1007/s10951-009-0129-5

Online Variable-Sized Bin Packing with Conflicts
Leah Epstein, Lene M. Favrholdt, and Asaf Levin
Discrete Optimization 8(2): 333-343, 2011

Comparing First-Fit and Next-Fit for Online Edge Coloring
Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai
Theoretical Computer Science 411:1734-1741, 2010
Preliminary version in the 19th ISAAC, LNCS 5369: 89-99, 2008

Scheduling Jobs on Grid Processors
Joan Boyar and Lene M. Favrholdt
Algorithmica 57(4):819-847, 2010.
Preliminary version in the 10th SWAT, LNCS 4059: 17-28, 2006

The Relative Worst-Order Ratio Applied to Paging
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen
Journal of Computer and System Sciences 73: 818-843, 2007.
Preliminary version in the 16th SODA, 718-727, 2005

The Relative Worst Order Ratio for On-Line Algorithms
Joan Boyar, Lene M. Favrholdt
ACM Transactions on Algorithms 3(2), 2007.
Preliminary version in the 5th CIAC, LNCS 2653: 58-69, 2003

Separating Online Scheduling Algorithms with the Relative Worst Order Ratio.
Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt
Journal of Combinatorial Optimization 12(4): 362-385, 2006.

The Maximum Resource Bin Packing Problem
J. Boyar, L. Epstein, L.M. Favrholdt, J.S. Kohrt, K.S. Larsen, M.M. Pedersen, S. Wøhlk
Theoretical Computer Science 362(1-3):127-139, 2006.
Preliminary version in the 15th FCT, LNCS 3623: 397-408, 2005

Optimal Non-Preemptive Semi-Online Scheduling on Two Related Machines
Leah Epstein, Lene M. Favrholdt
Journal of Algorithms 57(1): 49-73, 2005
Preliminary version in the 27th MFCS, LNCS 2420: 245-256, 2002

On Paging with Locality of Reference
Susanne Albers, Lene M. Favrholdt, Oliver Giel
Journal of Computer and System Sciences 70: 145-175, 2005
Preliminary version in th 34th STOC, 258-267, 2002

Extending the Accommodating Function
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
Acta Informatica 40: 3-35, 2003
Preliminary version in the 8th COCOON, LNCS 2387: 87-96, 2002

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins
Leah Epstein, Lene M. Favrholdt
Acta Cybernetica 16: 57-66, 2003
Preliminary version in the 8th COCOON, LNCS 2387: 467-475, 2002.

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
Journal of Scheduling 6(2): 131-147, 2003.

On-Line Edge Coloring with a Fixed Number of Colors
Lene M. Favrholdt, Morten N. Nielsen
Algorithmica 35(2): 176-191, 2003.
Preliminary version in the 20th FST TCS, LNCS 1974: 106-116, 2000

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

Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines
Leah Epstein, Lene M. Favrholdt
Operations Research Letters 30(4): 269-275, 2002

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

Fair versus Unrestricted Bin Packing
Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
Seventh Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 1851: 200-213, 2000

PhD Thesis

On-Line Problems with Restricted Input
Supervisor: Joan Boyar

Master's Thesis

Edge Coloring of Graphs (in Danish).
Supervisor: Bjarne Toft

Bachelor Project

Kortlægningsstrategi for skildpadderobot
Supervisor: Niels Jul Jacobsen