Search Results

Documents authored by Favrholdt, Lene M.

Document
DOI: 10.4230/LIPIcs.MFCS.2026.42
Forwarding Packets Greedily on the Line

Authors: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Kevin Schewior, and Rob van Stee

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right, and the packet arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the elapsed time between its release and its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al. in 2014, with a focus on line networks. They proposed several natural algorithms. For one, they proved that it is not O(1)-competitive; for others, they claimed analogous lower bounds, seemingly leaving no natural candidate for an O(1)-competitive algorithm. In this paper, we study a natural algorithm not considered in that work. Our algorithm, simply called Greedy, selects packets according to their projected flow time under the assumption that they are not delayed any further. We focus on the special case in which each packet needs to be forwarded by one or two routers; this case captures core difficulties. We show that Greedy achieves a competitive ratio of exactly 2-2^{1-k}, where k is the number of active routers in the network. We also give the first nontrivial general lower bound, which applies even to randomized algorithms: using the same type of instances as in our lower bound for Greedy, we show that no algorithm can be (4/3-ε)-competitive for any ε > 0.
Cite as

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Kevin Schewior, and Rob van Stee. Forwarding Packets Greedily on the Line. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.MFCS.2026.42,
  author =	{Boyar, Joan and Favrholdt, Lene M. and Larsen, Kim S. and Schewior, Kevin and van Stee, Rob},
  title =	{{Forwarding Packets Greedily on the Line}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.42},
  URN =		{urn:nbn:de:0030-drops-274230},
  doi =		{10.4230/LIPIcs.MFCS.2026.42},
  annote =	{Keywords: Online algorithms, Packet scheduling, Greedy algorithm}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.20
Online Unit Profit Knapsack with Untrusted Predictions

Authors: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a/â where a is the actual value for this average size and â is the prediction. The algorithm presented achieves a competitive ratio of 1/(2r) for r ≥ 1 and r/2 for r ≤ 1. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of r. Note that the result for accurate advice, r = 1, is only 1/2, but we show that no deterministic algorithm knowing the value a can achieve a competitive ratio better than (e-1)/e ≈ 0.6321 and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of r (e-1)/e for r ≤ 1 and (e-r)/e for 1 ≤ r < e, and no deterministic algorithm can be better for both r < 1 and 1 < r < e.
Cite as

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. Online Unit Profit Knapsack with Untrusted Predictions. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2022.20,
  author =	{Boyar, Joan and Favrholdt, Lene M. and Larsen, Kim S.},
  title =	{{Online Unit Profit Knapsack with Untrusted Predictions}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.20},
  URN =		{urn:nbn:de:0030-drops-161800},
  doi =		{10.4230/LIPIcs.SWAT.2022.20},
  annote =	{Keywords: online algorithms, untrusted predictions, knapsack problem, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.21
Online Dominating Set

Authors: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and not necessarily connected graphs. We believe this paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. In most cases, we obtain tight bounds on the competitive ratios. Our results show that requiring the graphs to be presented in a connected fashion allows the online algorithms to obtain provably better solutions. Furthermore, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.
Cite as

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen. Online Dominating Set. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2016.21,
  author =	{Boyar, Joan and Eidenbenz, Stephan J. and Favrholdt, Lene M. and Kotrbcik, Michal and Larsen, Kim S.},
  title =	{{Online Dominating Set}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.21},
  URN =		{urn:nbn:de:0030-drops-60434},
  doi =		{10.4230/LIPIcs.SWAT.2016.21},
  annote =	{Keywords: online algorithms, dominating set, competitive analysis, graph classes, connected graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.116
Advice Complexity for a Class of Online Problems

Authors: Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. We determine the advice complexity of a number of hard online problems including independent set, vertex cover, dominating set and several others. These problems are hard, since a single wrong answer by the online algorithm can have devastating consequences. For each of these problems, we show that \log\left(1+\frac{(c-1)^{c-1}}{c^{c}}\right)n=\Theta (n/c) bits of advice are necessary and sufficient (up to an additive term of O(\log n)) to achieve a competitive ratio of c. This is done by introducing a new string guessing problem related to those of Emek et al. (TCS 2011) and Böckenhauer et al. (TCS 2014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems. Previous results of Halldórsson et al. (TCS 2002) on online independent set, in a related model, imply that the advice complexity of the problem is \Theta (n/c). Our results improve on this by providing an exact formula for the higher-order term. Böckenhauer et al. (ISAAC 2009) gave a lower bound of \Omega (n/c) and an upper bound of O((n\log c)/c) on the advice complexity of online disjoint path allocation. We improve on the upper bound by a factor of $\log c$. For the remaining problems, no bounds on their advice complexity were previously known.
Cite as

Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Advice Complexity for a Class of Online Problems. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 116-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.STACS.2015.116,
  author =	{Boyar, Joan and Favrholdt, Lene M. and Kudahl, Christian and Mikkelsen, Jesper W.},
  title =	{{Advice Complexity for a Class of Online Problems}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{116--129},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.116},
  URN =		{urn:nbn:de:0030-drops-49086},
  doi =		{10.4230/LIPIcs.STACS.2015.116},
  annote =	{Keywords: online algorithms, advice complexity, asymmetric string guessing, advice complexity class AOC, covering designs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact