Search Results

Documents authored by Favrholdt, Lene M.

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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