The project Online Algorithms with Machine Learning Predictors is funded by a DKK 770,400 grant from the Independent Research Fund Denmark, Natural Sciences, running from January 1, 2021 through June 30, 2024.
The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The participants are members of the Algorithms group and are all associated with the Research Training Program in Computer Science as Ph.D. advisors.

Activities

Almost all activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests.

Publications

Here we will list project publications when the project starts. Slightly older publications can be found on the page for our previous project. Complete lists for each participant can be found via our individual home pages or via dblp, the standard search engine for Computer Science publications. We link to the official site for published papers using the doi (digital object identifier) of the papers. For open access versions, we refer to each author's own home page.

Acknowledgement: We are grateful to dblp (2024-09-11) for providing data for the publication list.

Peer-Reviewed International Journal Articles

Stochastic Probing with Increasing Precision.
Martin Hoefer, Kevin Schewior, Daniel Schmand.
SIAM J. Discret. Math. 38(1): 148-169, 2024.

Online Unit Profit Knapsack with Predictions.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
Algorithmica 86(9): 2786-2821, 2024.

Advice complexity of adaptive priority algorithms.
Joan Boyar, Kim S. Larsen, Denis Pankratov.
Theor. Comput. Sci. 984: 114318, 2024.

Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios.
Benedikt M. Plank, Kevin Schewior.
SIAM J. Discret. Math. 38(3): 2069-2088, 2024.

Improved Bounds for Open Online Dial-a-Ride on the Line.
Alexander Birx, Yann Disser, Kevin Schewior.
Algorithmica 85(5): 1372-1414, 2023.

Online Throughput Maximization on Unrelated Machines: Commitment is No Burden.
Franziska Eberle, Nicole Megow, Kevin Schewior.
ACM Trans. Algorithms 19(1): 10:1-10:25, 2023.

Relaxing the Irrevocability Requirement for Online Graph Algorithms.
Joan Boyar, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
Algorithmica 84(7): 1916-1951, 2022.

Relative Worst-order Analysis: A Survey.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
ACM Comput. Surv. 54(1): 8:1-8:21, 2022.

Online Bin Covering with Advice.
Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen.
Algorithmica 83(3): 795-821, 2021.

Peer-Reviewed International Conference Articles

On the Online Weighted Non-Crossing Matching Problem.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, Denis Pankratov.
SWAT, LIPIcs 294: 16:1-16:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024, June 12-14, 2024, Helsinki, Finland.]

Quickly Determining Who Won an Election.
Lisa Hellerstein, Naifeng Liu, Kevin Schewior.
ITCS, LIPIcs 287: 61:1-61:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA.]

Paging with Succinct Predictions.
Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon.
ICML, Proceedings of Machine Learning Research 202: 952-968, PMLR, 2023.
[International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA.]

Trading Prophets.
José Correa, Andrés Cristi, Paul Duetting, MohammadTaghi Hajiaghayi, Jan Olkowski, Kevin Schewior.
EC: 490-510, ACM, 2023.
[Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023.]

Threshold Testing and Semi-Online Prophet Inequalities.
Martin Hoefer, Kevin Schewior.
ESA, LIPIcs 274: 62:1-62:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands.]

Online Minimum Spanning Trees with Weight Predictions.
Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 14079: 136-148, Springer, 2023.
[Algorithms and Data Structures - 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 - August 2, 2023, Proceedings.]

Online Algorithms with Predictions (Invited Talk).
Joan Boyar.
MFCS, LIPIcs 272: 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France.]

Quotable Signatures for Authenticating Shared Quotes.
Joan Boyar, Simon Erfurth, Kim S. Larsen, Ruben Niederhagen.
LATINCRYPT, Lecture Notes in Computer Science 14168: 273-292, Springer, 2023.
[Progress in Cryptology - LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings.]

Online Interval Scheduling with Predictions.
Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 14079: 193-207, Springer, 2023.
[Algorithms and Data Structures - 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 - August 2, 2023, Proceedings.]

Incremental Maximization via Continuization.
Yann Disser, Max Klimm, Kevin Schewior, David Weckbecker.
ICALP, LIPIcs 261: 47:1-47:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany.]

Improved Approximation Algorithms for the Expanding Search Problem.
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, Kevin Schewior.
ESA, LIPIcs 274: 54:1-54:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands.]

Knapsack Secretary Through Boosting.
Andreas Abels, Leon Ladewig, Kevin Schewior, Moritz Stinzendörfer.
WAOA, Lecture Notes in Computer Science 13538: 61-81, Springer, 2022.
[Approximation and Online Algorithms - 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8-9, 2022, Proceedings.]

Online Unit Profit Knapsack with Untrusted Predictions.
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
SWAT, LIPIcs 227: 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
[18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands.]

 

Data protection at SDU ▪ Databeskyttelse på SDU