Search Results

Documents authored by van Stee, Rob

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.16
A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs

Authors: Felix Höhne and Rob van Stee

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
In the discrete bamboo garden trimming problem we are given n bamboo that grow at rates v_1,… ,v_n per day. Each day a robotic gardener cuts down one bamboo to height 0. The goal is to find a schedule that minimizes the height of the tallest bamboo that ever exists. We present a 10/7-approximation algorithm that is based on a reduction to the pinwheel problem. This is consistent with the approach of earlier algorithms, but some new techniques are used that lead to a better approximation ratio. We also consider the continuous version of the problem where the gardener travels in a metric space between plants and cuts down a plant each time he reaches one. We show that on the star graph the previously proposed algorithm Reduce-Fastest is a 6-approximation and the known Deadline-Driven Strategy is a (3+2√2)-approximation. The Deadline-Driven Strategy is also a (9+2√5)-approximation on star graphs with multiple plants on each branch.
Cite as

Felix Höhne and Rob van Stee. A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hohne_et_al:LIPIcs.APPROX/RANDOM.2023.16,
  author =	{H\"{o}hne, Felix and van Stee, Rob},
  title =	{{A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.16},
  URN =		{urn:nbn:de:0030-drops-188417},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.16},
  annote =	{Keywords: bamboo garden trimming, approximation algorithms, scheduling}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.41
Beating the Harmonic Lower Bound for Online Bin Packing

Authors: Sandy Heydrich and Rob van Stee

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. Harmonic++ achieves a competitive ratio of 1.58889 and belongs to the Super Harmonic framework [Seiden, J. ACM, 2002]; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved [Ramanan et al., J. Algorithms, 1989]. In this paper, we present an online bin packing algorithm with asymptotic performance ratio of 1.5815, which constitutes the first improvement in fifteen years and reduces the gap to the lower bound by roughly 15%. We make two crucial changes to the Super Harmonic framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of only their types. In particular, for item pairs where the size of one item is in (1/3,1/2] and the other is larger than 1/2 (a large item), when deciding whether to pack such a pair together in one bin, our algorithm does not consider their types, but only checks whether their total size is at most 1. Second, for items with sizes in (1/3,1/2] (medium items), we try to pack the larger items of every type in pairs, while combining the smallest items with large items whenever possible. To do this, we postpone the coloring of medium items (i.e., the decision which items to pack in pairs and which to pack alone) where possible, and later select the smallest ones to be reserved for combining with large items. Additionally, in case such large items arrive early, we pack medium items with them whenever possible. This is a highly unusual idea in the context of Harmonic-like algorithms, which initially seems to preclude analysis (the ratio of items combined with large items is no longer a fixed constant). For the analysis, we carefully mark medium items depending on how they end up packed, enabling us to add crucial constraints to the linear program used by Seiden. We consider the dual, eliminate all but one variable and then solve it with the ellipsoid method using a separation oracle. Our implementation uses additional algorithmic ideas to determine previously hand set parameters automatically and gives certificates for easy verification of the results. We give a lower bound of 1.5766 for algorithms like ours. This shows that fundamentally different ideas will be required to make further improvements
Cite as

Sandy Heydrich and Rob van Stee. Beating the Harmonic Lower Bound for Online Bin Packing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{heydrich_et_al:LIPIcs.ICALP.2016.41,
  author =	{Heydrich, Sandy and van Stee, Rob},
  title =	{{Beating the Harmonic Lower Bound for Online Bin Packing}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.41},
  URN =		{urn:nbn:de:0030-drops-63214},
  doi =		{10.4230/LIPIcs.ICALP.2016.41},
  annote =	{Keywords: Bin packing, online algorithms, harmonic algorithm}
}
Document
DOI: 10.4230/DagSemProc.07261.10
Maximizing the Minimum Load for Selfisch Agents

Authors: Leah Epstein and Rob van Stee

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
We consider the problem of maximizing the minimum load for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. Unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. For a constant number of machines, $m$, we show a monotone polynomial time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We also present an FPTAS for the classical machine covering problem, i.e., where no selfish agents are involved (the previous best result for this case was a PTAS) and use this to give a monotone FPTAS. Additionally, we give a monotone approximation algorithm with approximation ratio $min(m,(2+eps)s_1/s_m)$ where $eps>0$ can be chosen arbitrarily small and $s_i$ is the (real) speed of machine $i$. Finally we give improved results for two machines.
Cite as

Leah Epstein and Rob van Stee. Maximizing the Minimum Load for Selfisch Agents. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:DagSemProc.07261.10,
  author =	{Epstein, Leah and van Stee, Rob},
  title =	{{Maximizing the Minimum Load for Selfisch Agents}},
  booktitle =	{Fair Division},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.10},
  URN =		{urn:nbn:de:0030-drops-12427},
  doi =		{10.4230/DagSemProc.07261.10},
  annote =	{Keywords: Scheduling, algorithmic mechanism design, maximizing minimum load}
}
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