DROPS

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.9

Approximation Algorithms and Lower Bounds for Graph Burning

Authors: Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann

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

Abstract

Graph Burning models information spreading in a given graph as a process such that in each step one node is infected (informed) and also the infection spreads to all neighbors of previously infected nodes. Formally, given a graph G = (V,E), possibly with edge lengths, the burning number b(G) is the minimum number g such that there exist nodes v_0,…,v_{g-1} ∈ V satisfying the property that for each u ∈ V there exists i ∈ {0,…,g-1} so that the distance between u and v_i is at most i. We present a randomized 2.314-approximation algorithm for computing the burning number of a general graph, even with arbitrary edge lengths. We complement this by an approximation lower bound of 2 for the case of equal length edges, and a lower bound of 4/3 for the case when edges are restricted to have length 1. This improves on the previous 3-approximation algorithm and an APX-hardness result.

Cite as

Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann. Approximation Algorithms and Lower Bounds for Graph Burning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lieskovsky_et_al:LIPIcs.APPROX/RANDOM.2023.9,
  author =	{Lieskovsk\'{y}, Matej and Sgall, Ji\v{r}{\'\i} and Feldmann, Andreas Emil},
  title =	{{Approximation Algorithms and Lower Bounds for Graph Burning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{9:1--9:17},
  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.9},
  URN =		{urn:nbn:de:0030-drops-188345},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.9},
  annote =	{Keywords: Graph Algorithms, approximation Algorithms, randomized Algorithms}
}

Search Results

Documents authored by Lieskovský, Matej

Improved Online Load Balancing with Known Makespan

Abstract

Cite as

Approximation Algorithms and Lower Bounds for Graph Burning

Abstract

Cite as

Thanks for your feedback!

Could not send message