(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science

   

Publications

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

Batch Coloring of Graphs
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin
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
27th International Workshop on Combinatorial Algorithms
LNCS 9843: 179-190, 2016

Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene Favrholdt, Michal Kotrbcik and Kim S. Larsen
15th Scandinavian Symposium and Workshops on Algorithm Theory
LIPIcs 53: 21:1-21:15, 2016

Online Bounded Analysis
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
11th International Computer Science Symposium in Russia
LNCS 9691: 131-145, 2016

Advice Complexity for a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen
To appear in Theory of Computing Systems
Preliminary version in 32nd International Symposium on Theoretical Aspects of Computer Science (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 Dual Edge Coloring of Paths and Trees
Lene M. Favrholdt and Jesper W. Mikkelsen
Twelfth Workshop on Approximation and Online Algorithms (WAOA), LNCS 8952: 181-192, 2014
To appear in Acta Informatica

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

Title: "On-Line Problems with Restricted Input"
Supervisor: Joan Boyar

Master's Thesis

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