![[topimage]](IMADA_en.png)
On-Line Algorithms and Advice
On-Line Algorithms and Advice (OLAA) is funded by a DKK 2,900,101.00 grant from VILLUM FONDEN from September 17, 2013 through September 16, 2017.Participants
PhD students
- Christian Kudahl (started December 1, 2013, and submitted dissertation entitled "On the Nature of Online Computation" November 30, 2016. Successfully defended on March 21, 2017.)
- Jesper With Mikkelsen (started January 1, 2014, and submitted a dissertation entitled "Online Decision-Making with Advice: Complexity and Algorithms" on February 25, 2017. Successfully defended on March 22, 2017.)
Postdoc
- Michal Kotrbčik (September 1, 2015, to August 31, 2016)
Environment
The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The group of participants and PhD students is associated with the Research Training Program in Computer Science.A Survey on Online Algorithms with Advice
The group wrote an extensive survey on online algorithms with advice:ACM Computing Surveys, 50(2), Article No. 19, 2017.
Open access here.
Earlier version, invited contribution, in SIGACT News, 47: 93-129, 2016.
External Activities
Special Session on Online Algorithms at CiE 2014
Co-organized by Joan Boyar and Csánad Imreh.
Invited speakers: Jiri Sgall, Kim Skak Larsen, Adi Rosen, Rob van Stee.-
Workshop associated with ICALP 2014: Trends in On-Line Algorithms (TOLA 2104)
Organizing committee: Joan Boyar (chair), Lene Monrad Favrholdt, Kim Skak Larsen.
Program committee: Lene Monrad Favrholdt (chair), Yossi Azar, Marek Chrobak, Leah Epstein, Alejandro López-Ortiz. -
EURO Summer Institute on Online Optimization at the University of Szeged, June 2015.
Senior keynote speaker and member of the scientific committee: Joan Boyar -
Workshop - New Techniques in Online Algorithms, November 12-13, 2015, Paris.
Attended by the entire group.
Presentations given by Christian Kudahl, Jesper With Mikkeslen, and Joan Boyar.
Peer-Reviewed International Conference and Journal Articles (since project start)
- Batch Coloring of Graphs.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Accepted for publication in Algorithmica. Open access on arXiv.org. - Online-Bounded Analysis.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Accepted for publication in Journal of Scheduling. Open access on arXiv.org. - Weighted Online Problems with Advice.
- Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper With Mikkelsen.
Accepted for publication in Theory of Computing Systems. Open access on arXiv.org. - Adding Isolated Vertices Makes some Greedy Online Algorithms Optimal.
- Joan Boyar and Christian Kudahl.
To appear in Discrete Applied Mathematics. Open access on arXiv.org. - Online Dual Edge Coloring of Paths and Trees.
- Lene M. Favrholdt and Jesper W. Mikkelsen.
To appear in Acta Informatica. Open access on arXiv.org. - The Advice Complexity of a Class of Hard Online Problems.
- Joan Boyar, Lene Monrad Favrholdt, Christian Kudahl, and Jesper With Mikkelsen.
Theory of Computing Systems, 61: 1128-1177, 2017.
Open access on arXiv.org. - Relaxing the Irrevocability Requirement for Online Graph Algorithms.
- Joan Boyar, Lene M. Favrholdt, Michal Kotrbčik, and Kim S. Larsen.
In Algorithms and Data Structures Symposium (WADS 2017), volume 10389 of Lecture Notes in Computer Science, pages 217-228, Springer, 2017. Open access on arXiv.org. - Batch Coloring of Graphs.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
In 14th Workshop on Approximation and Online Algorithms (WAOA 2016), volume 10138 of Lecture Notes in Computer Science, pages 52-64, Springer, 2017. Open access on arXiv.org. - Advice Complexity of the Online Induced Subgraph Problem.
- Dennis Komm, Rastislav Královic, Richard Královic and Christian Kudahl.
In 41st International Symposium on Mathematical Foundations of Computer Science, (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics, pages 59:1-59:13, 2016. - Advice Complexity of the Online Search Problem.
- Jhoirene Clemente, Juraj Hromkovic, Dennis Komm, and Christian Kudahl.
In 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), volume 9843 of Lecture Notes in Computer Science, pages 203-212, Springer, 2016. Open access on arXiv.org. - Weighted Online Problems with Advice.
- Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper With Mikkelsen.
In 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), volume 9843 of Lecture Notes in Computer Science, pages 179-190, Springer, 2016. Open access on arXiv.org. - Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation.
- Jesper W. Mikkelsen.
In 43rd International Colloquium on Automata, Languages, and Programming, (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics, pages 39:1-39:14, 2016. - Online Dominating Set
- Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbčik, and Kim S. Larsen.
In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics, pages 21:1-21:15, 2016. - Online Bounded Analysis.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
In 11th International Computer Science Symposium in Russia (CSR 2016), volume 9691 of Lecture Notes in Computer Science, pages 131-145, Springer, 2016. Open access on arXiv.org. - On the List Update Problem with Advice.
- Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
Final version in Information and Computation, 253: 411-423, 2017.
Open access on arXiv.org. - Online Bin Packing with Advice.
- Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
Final version in Algorithmica, 74: 507-527, 2016.
Open access here. - Equimatchable Graphs on Surfaces.
- Eduard Eiben and Michal Kotrbčik.
Final version in Journal of Graph Theory, 81: 35-49, 2016. Open access on arXiv.org. - Adding Isolated Vertices Makes Some Online Algorithms Optimal.
- Joan Boyar and Christian Kudahl.
Final version in 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), volume 9538 of Lecture Notes in Computer Science, pages 65-76, Springer, 2015. Open access on arXiv.org. - Optimal Online Edge Coloring of Planar Graphs with Advice.
- Jesper W. Mikkelsen.
Final version in 9th International Conference on Algorithms and Complexity, (CIAC 2015), volume 9079 of Lecture Notes in Computer Science, pages 352-364, Springer, 2015. Open access on arXiv.org. - Deciding the On-line Chromatic Number of a Graph with Pre-coloring is PSPACE-complete.
- Christian Kudahl.
Final version in 9th International Conference on Algorithms and Complexity, (CIAC 2015), volume 9079 of Lecture Notes in Computer Science, pages 313-324, Springer, 2015. Open access on arXiv.org. - Genus of the cartesian product of triangles.
- Michal Kotrbčik and Tomaž Pisanski.
Final version in Electronic Journal of Combinatorics, 22 (4): #P4.2, 2015. Open access journal. - Advice Complexity for a Class of Online Problems.
- Joan Boyar, Lene Monrad Favrholdt, Christian Kudahl, and Jesper With Mikkelsen.
In 32st Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics, pages 116-129, 2015. - Online Multi-Coloring with Advice.
- Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Final version in Theoretical Computer Science, 596: 79-91, 2015. Open access on arXiv.org. - The Frequent Items Problem in Online Streaming under Various Performance Measures.
- Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
Final version in International Journal of Foundations of Computer Science, 26: 413-439.
Open access here. - Relative Interval Analysis of Paging Algorithms on Access Graphs.
- Joan Boyar, Sushmita Gupta, and Kim S. Larsen.
Final verison in Theoretical Computer Science, 568: 28-48, 2015.
Open access here. - Online Multi-Coloring with Advice.
- Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Final version in 12th Workshop on Approximation and Online Algorithms (WAOA 2014), volume 8952 of Lecture Notes in Computer Science, pages 83-94, Springer, 2015. Open access on arXiv.org. - Online Dual Edge Coloring of Paths and Trees.
- Lene M. Favrholdt and Jesper W. Mikkelsen.
Final version in 12th Workshop on Approximation and Online Algorithms (WAOA 2014), volume 8952 of Lecture Notes in Computer Science, pages 181-192, Springer, 2015. Open access on arXiv.org. - Online Bin Covering: Expectations vs. Guarantees.
- Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Theoretical Computer Science, 556: 71-84, 2014. Open access on author's home page. - A Comparison of Performance Measures for Online Algorithms.
- Joan Boyar, Sandy Irani, and Kim S. Larsen
Final version in Algorithmica, 72: 969-994, 2015. Open access on arXiv.org. - A Comparison of Performance Measures via Online Search.
- Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
Final version in Theoretical Computer Science, 532: 2-13, 2014. Open access on arXiv.org. - On the List Update Problem with Advice.
- Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
Final version in 8th International Conference on Language and Automata Theory and Applications (LATA 2014), volume 8370 of Lecture Notes in Computer Science, pages 210-221, Springer, 2014. Open access on arXiv.org. - Online Bin Packing with Advice.
- Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
In 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics, pages 174-186, 2014. - Online Bin Covering: Expectations vs. Guarantees.
- Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Final version in Seventh Annual International Conference on Combinatorial Optimization and Applications (COCOA), volume 8287 of Lecture Notes in Computer Science, pages 226-237. Springer, 2013. Open access on arXiv.org.