Search Results

Documents authored by Buchem, Moritz

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.14
Scheduling on a Stochastic Number of Machines

Authors: Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado, Kevin Schewior, and Andreas Wiese

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

Abstract
We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only after all jobs are assigned to a given number of bags, the actual number of machines is revealed. Subsequently, the jobs need to be assigned to the machines without splitting the bags. This is the stochastic version of a related problem introduced by Stein and Zhong [SODA 2018, TALG 2020] and it is, for example, motivated by bundling jobs that need to be scheduled by data centers. We present two PTASs for the stochastic setting, computing job-to-bag assignments that (i) minimize the expected maximum machine load and (ii) maximize the expected minimum machine load (like in the Santa Claus problem), respectively. The former result follows by careful enumeration combined with known PTASs. For the latter result, we introduce an intricate dynamic program that we apply to a suitably rounded instance.
Cite as

Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado, Kevin Schewior, and Andreas Wiese. Scheduling on a Stochastic Number of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchem_et_al:LIPIcs.APPROX/RANDOM.2024.14,
  author =	{Buchem, Moritz and Eberle, Franziska and Kasuya Rosado, Hugo Kooki and Schewior, Kevin and Wiese, Andreas},
  title =	{{Scheduling on a Stochastic Number of Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{14:1--14:15},
  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.14},
  URN =		{urn:nbn:de:0030-drops-210073},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.14},
  annote =	{Keywords: scheduling, approximation algorithms, stochastic machines, makespan, max-min fair allocation, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.26
Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically

Authors: Moritz Buchem, Paul Deuker, and Andreas Wiese

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
One important goal in algorithm design is determining the best running time for solving a problem (approximately). For some problems, we know the optimal running time, assuming certain conditional lower bounds. In this paper, we study the d-dimensional geometric knapsack problem in which we are far from this level of understanding. We are given a set of weighted d-dimensional geometric items like squares, rectangles, or hypercubes and a knapsack which is a square or a (hyper-)cube. Our goal is to select a subset of the given items that fit non-overlappingly inside the knapsack, maximizing the total profit of the packed items. We make a significant step towards determining the best running time for solving these problems approximately by presenting approximation algorithms whose running times are near-linear, i.e., O(n⋅poly(log n)), for any constant d and any parameter ε > 0 (the exponent of log n depends on d and 1/ε). In the case of (hyper)-cubes, we present a (1+ε)-approximation algorithm. This improves drastically upon the currently best known algorithm which is a (1+ε)-approximation algorithm with a running time of n^{O_{ε,d}(1)} where the exponent of n depends exponentially on 1/ε and d. In particular, our algorithm is an efficient polynomial time approximation scheme (EPTAS). Moreover, we present a (2+ε)-approximation algorithm for rectangles in the setting without rotations and a (17/9+ε)≈ 1.89-approximation algorithm if we allow rotations by 90 degrees. The best known polynomial time algorithms for this setting have approximation ratios of 17/9+ε and 1.5+ε, respectively, and running times in which the exponent of n depends exponentially on 1/ε. In addition, we give dynamic algorithms with polylogarithmic query and update times, having the same approximation guarantees as our other algorithms above. Key to our results is a new family of structured packings which we call easily guessable packings. They are flexible enough to guarantee the existence of profitable solutions while providing enough structure so that we can compute these solutions very quickly.
Cite as

Moritz Buchem, Paul Deuker, and Andreas Wiese. Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchem_et_al:LIPIcs.SoCG.2024.26,
  author =	{Buchem, Moritz and Deuker, Paul and Wiese, Andreas},
  title =	{{Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.26},
  URN =		{urn:nbn:de:0030-drops-199716},
  doi =		{10.4230/LIPIcs.SoCG.2024.26},
  annote =	{Keywords: Geometric packing, approximation algorithms, dynamic algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.42
Additive Approximation Schemes for Load Balancing Problems

Authors: Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_{max}, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ε⋅ p_{max}.
Cite as

Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchem_et_al:LIPIcs.ICALP.2021.42,
  author =	{Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas},
  title =	{{Additive Approximation Schemes for Load Balancing Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.42},
  URN =		{urn:nbn:de:0030-drops-141116},
  doi =		{10.4230/LIPIcs.ICALP.2021.42},
  annote =	{Keywords: Load balancing, Approximation schemes, Parallel machine scheduling}
}
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 About DROPS Imprint Privacy Contact