8 Search Results for "van Stee, Rob"

Document
DOI: 10.4230/LIPIcs.ESA.2025.108
Deterministic Approximation Algorithm for Graph Burning

Authors: Matej Lieskovský

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Graph Burning models a contagion spreading in a network as a process such that in each step one node is infected and also the infection spreads to all neighbors of previously infected nodes. Formally, the burning number b(G) of a given graph G = (V,E), possibly with edge lengths, is the minimum number g such that there exists a sequence of nodes v₁,…,v_g satisfying the property that for each w ∈ V there exists i ∈ {1,…,g} so that the distance between w and v_i is at most g-i. We present an elegant deterministic 2.314-approximation algorithm for the Graph Burning problem on general graphs with arbitrary edge lengths. This algorithm matches the approximation ratio of the previous randomized 2.314-approximation algorithm and improves on the previous deterministic 3-approximation algorithm.
Cite as

Matej Lieskovský. Deterministic Approximation Algorithm for Graph Burning. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 108:1-108:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lieskovsky:LIPIcs.ESA.2025.108,
  author =	{Lieskovsk\'{y}, Matej},
  title =	{{Deterministic Approximation Algorithm for Graph Burning}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{108:1--108:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.108},
  URN =		{urn:nbn:de:0030-drops-245775},
  doi =		{10.4230/LIPIcs.ESA.2025.108},
  annote =	{Keywords: Graph Algorithms, Approximation Algorithms, Graph Burning}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.10
Improved Approximation Guarantees for Advertisement Placement

Authors: Waldo Gálvez, Roberto Oliva, and Victor Verdugo

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

Abstract
The advertisement placement problem involves selecting and scheduling ads within a timeline that has capacity constraints to maximize profit. Each task is characterized by its height, width, and profit, and must be fully scheduled across multiple time slots. This problem models practical scenarios such as internet advertising and energy management, and it also generalizes classical combinatorial optimization problems like the knapsack and bin packing problems. We present a simple (2+ε)-approximation algorithm for any ε > 0, which improves upon the state-of-the-art 3+ε factor established by Freund and Naor twenty years ago. Our approach combines rounding techniques with dynamic programming and an efficient extension of list scheduling. Furthermore, we enhance this method with linear programming techniques to provide an almost optimal (1+ε)-approximation algorithm under resource augmentation, which allows for a slight increase in time slot capacities.
Cite as

Waldo Gálvez, Roberto Oliva, and Victor Verdugo. Improved Approximation Guarantees for Advertisement Placement. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2025.10,
  author =	{G\'{a}lvez, Waldo and Oliva, Roberto and Verdugo, Victor},
  title =	{{Improved Approximation Guarantees for Advertisement Placement}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  URN =		{urn:nbn:de:0030-drops-243762},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  annote =	{Keywords: Advertisement Placement, Two-dimensional Packing, Geometric Knapsack, Resource Allocation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.104
Improved Approximation Algorithms for Three-Dimensional Bin Packing

Authors: Debajyoti Kar, Arindam Khan, and Malin Rau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin - giving an (absolute) approximation hardness of 2 for 3D-BP and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε > 0. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T_{∞}² + ε ≈ 2.86, where T_{∞} is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3 T_{∞}/2 + ε ≈ 2.54. Further, we show that unlike 3D-BP (and 3D-SP), 3D-MVBB admits an APTAS.
Cite as

Debajyoti Kar, Arindam Khan, and Malin Rau. Improved Approximation Algorithms for Three-Dimensional Bin Packing. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ICALP.2025.104,
  author =	{Kar, Debajyoti and Khan, Arindam and Rau, Malin},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Bin Packing}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.104},
  URN =		{urn:nbn:de:0030-drops-234814},
  doi =		{10.4230/LIPIcs.ICALP.2025.104},
  annote =	{Keywords: Approximation Algorithms, Geometric Packing, Multidimensional Packing}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.10
Improved Online Load Balancing with Known Makespan

Authors: Martin Böhm, Matej Lieskovský, Sören Schmitt, Jiří Sgall, and Rob van Stee

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

Abstract
We break the barrier of 3/2 for the problem of online load balancing with known makespan, also known as bin stretching. In this problem, m identical machines and the optimal makespan are given. The load of a machine is the total size of all the jobs assigned to it and the makespan is the maximum load of all the machines. Jobs arrive online and the goal is to assign each job to a machine while staying within a small factor (the competitive ratio) of the optimal makespan. We present an algorithm that maintains a competitive ratio of 139/93 < 1.495 for sufficiently large values of m, improving the previous bound of 3/2. The value 3/2 represents a natural bound for this problem: as long as the online bins are of size at least 3/2 of the offline bin, all items that fit at least two times in an offline bin have two nice properties. They fit three times in an online bin and a single such item can be packed together with an item of any size in an online bin. These properties are now both lost, which means that putting even one job on a wrong machine can leave some job unassigned at the end. It also makes it harder to determine good thresholds for the item types. This was one of the main technical issues in getting below 3/2. The analysis consists of an intricate mixture of size and weight arguments.
Cite as

Martin Böhm, Matej Lieskovský, Sören Schmitt, Jiří Sgall, and Rob van Stee. Improved Online Load Balancing with Known Makespan. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.APPROX/RANDOM.2024.10,
  author =	{B\"{o}hm, Martin and Lieskovsk\'{y}, Matej and Schmitt, S\"{o}ren and Sgall, Ji\v{r}{\'\i} and van Stee, Rob},
  title =	{{Improved Online Load Balancing with Known Makespan}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.10},
  URN =		{urn:nbn:de:0030-drops-210032},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.10},
  annote =	{Keywords: Online algorithms, bin stretching, bin packing}
}
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}
}
Document
DOI: 10.4230/DagSemProc.05031.21
Online scheduling of splittable tasks

Authors: Leah Epstein and Rob van Stee

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We consider online scheduling of splittable tasks on parallel machines. In our model, each task can be split into a limited number of parts, that can then be scheduled independently. We consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. We design a class of algorithms which allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. For identical machines we also improve upon the natural greedy algorithm in other classes of cases.
Cite as

Leah Epstein and Rob van Stee. Online scheduling of splittable tasks. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:DagSemProc.05031.21,
  author =	{Epstein, Leah and Stee, Rob van},
  title =	{{Online scheduling of splittable tasks}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.21},
  URN =		{urn:nbn:de:0030-drops-743},
  doi =		{10.4230/DagSemProc.05031.21},
  annote =	{Keywords: online scheduling , splittable tasks , parallel machines , greedy algorithm}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2024
  • 1 2023
  • 1 2016
  • 1 2007
  • Show More...

  • Refine by Author
  • 4 van Stee, Rob
  • 2 Epstein, Leah
  • 2 Lieskovský, Matej
  • 1 Böhm, Martin
  • 1 Gálvez, Waldo
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Packing and covering problems
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 1 Advertisement Placement
  • 1 Bin packing
  • 1 Geometric Knapsack
  • 1 Geometric Packing
  • Show More...

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact