Found 3 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

The total area of the 24 squares of sizes 1,2,…,24 is equal to the area of the 70× 70 square. Can this equation be demonstrated by a tiling of the 70× 70 square with the 24 squares of sizes 1,2,…,24? The answer is "NO", no such tiling exists. This has been demonstrated by computer search. However, until now, no proof without use of computer was given. We fill this gap and give a complete combinatorial proof.

Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, and Zsolt Tuza. No Tiling of the 70 × 70 Square with Consecutive Squares. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sgall_et_al:LIPIcs.FUN.2024.28, author = {Sgall, Ji\v{r}{\'\i} and Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Hvattum, Lars Magnus and Tuza, Zsolt}, title = {{No Tiling of the 70 × 70 Square with Consecutive Squares}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.28}, URN = {urn:nbn:de:0030-drops-199362}, doi = {10.4230/LIPIcs.FUN.2024.28}, annote = {Keywords: square packing, Gardner’s problem, combinatorial proof} }

Document

APPROX

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

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.

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} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003].
In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances.
We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.ISAAC.2016.21, author = {B\"{o}hm, Martin and Chrobak, Marek and Jez, Lukasz and Li, Fei and Sgall, Jir{\'\i} and Vesel\'{y}, Pavel}, title = {{Online Packet Scheduling with Bounded Delay and Lookahead}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.21}, URN = {urn:nbn:de:0030-drops-67901}, doi = {10.4230/LIPIcs.ISAAC.2016.21}, annote = {Keywords: buffer management, online scheduling, online algorithm, lookahead} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12, author = {Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel}, title = {{Online Algorithms for Multi-Level Aggregation}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.12}, URN = {urn:nbn:de:0030-drops-63637}, doi = {10.4230/LIPIcs.ESA.2016.12}, annote = {Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7.
We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins.
Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins.
Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

György Dósa and Jiri Sgall. First Fit bin packing: A tight analysis. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 538-549, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{dosa_et_al:LIPIcs.STACS.2013.538, author = {D\'{o}sa, Gy\"{o}rgy and Sgall, Jiri}, title = {{First Fit bin packing: A tight analysis}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {538--549}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.538}, URN = {urn:nbn:de:0030-drops-39630}, doi = {10.4230/LIPIcs.STACS.2013.538}, annote = {Keywords: Approximation algorithms, online algorithms, bin packing, First Fit} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Collection of the open problems presented at the scheduling seminar.

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3, author = {Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.}, title = {{10071 Open Problems – Scheduling}}, booktitle = {Scheduling}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10071}, editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3}, URN = {urn:nbn:de:0030-drops-25367}, doi = {10.4230/DagSemProc.10071.3}, annote = {Keywords: Open problems, scheduling} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.

Tomas Ebenlendr and Jiri Sgall. Semi-Online Preemptive Scheduling: One Algorithm for All Variants. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 349-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ebenlendr_et_al:LIPIcs.STACS.2009.1840, author = {Ebenlendr, Tomas and Sgall, Jiri}, title = {{Semi-Online Preemptive Scheduling: One Algorithm for All Variants}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {349--360}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1840}, URN = {urn:nbn:de:0030-drops-18406}, doi = {10.4230/LIPIcs.STACS.2009.1840}, annote = {Keywords: On-line algorithms, Scheduling} }

Document

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

We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques presented cover charging schemes, potential function arguments, and lower bounds based on Yao's principle. The studied problem is equivalent to the following buffer management problem: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The presented algorithms improve upon 2-competitive greedy algorithm, the competitive ratio is 1.939 for deterministic and 1.582 for randomized algorithms.

Jiri Sgall. Online Scheduling. 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{sgall:DagSemProc.05031.20, author = {Sgall, Jiri}, title = {{Online Scheduling}}, 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.20}, URN = {urn:nbn:de:0030-drops-695}, doi = {10.4230/DagSemProc.05031.20}, annote = {Keywords: online algorithms , scheduling} }

Document

**Published in:** LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

The total area of the 24 squares of sizes 1,2,…,24 is equal to the area of the 70× 70 square. Can this equation be demonstrated by a tiling of the 70× 70 square with the 24 squares of sizes 1,2,…,24? The answer is "NO", no such tiling exists. This has been demonstrated by computer search. However, until now, no proof without use of computer was given. We fill this gap and give a complete combinatorial proof.

Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, and Zsolt Tuza. No Tiling of the 70 × 70 Square with Consecutive Squares. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sgall_et_al:LIPIcs.FUN.2024.28, author = {Sgall, Ji\v{r}{\'\i} and Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Hvattum, Lars Magnus and Tuza, Zsolt}, title = {{No Tiling of the 70 × 70 Square with Consecutive Squares}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.28}, URN = {urn:nbn:de:0030-drops-199362}, doi = {10.4230/LIPIcs.FUN.2024.28}, annote = {Keywords: square packing, Gardner’s problem, combinatorial proof} }

Document

APPROX

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

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.

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} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003].
In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances.
We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.ISAAC.2016.21, author = {B\"{o}hm, Martin and Chrobak, Marek and Jez, Lukasz and Li, Fei and Sgall, Jir{\'\i} and Vesel\'{y}, Pavel}, title = {{Online Packet Scheduling with Bounded Delay and Lookahead}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.21}, URN = {urn:nbn:de:0030-drops-67901}, doi = {10.4230/LIPIcs.ISAAC.2016.21}, annote = {Keywords: buffer management, online scheduling, online algorithm, lookahead} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12, author = {Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel}, title = {{Online Algorithms for Multi-Level Aggregation}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.12}, URN = {urn:nbn:de:0030-drops-63637}, doi = {10.4230/LIPIcs.ESA.2016.12}, annote = {Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7.
We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins.
Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins.
Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

György Dósa and Jiri Sgall. First Fit bin packing: A tight analysis. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 538-549, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{dosa_et_al:LIPIcs.STACS.2013.538, author = {D\'{o}sa, Gy\"{o}rgy and Sgall, Jiri}, title = {{First Fit bin packing: A tight analysis}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {538--549}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.538}, URN = {urn:nbn:de:0030-drops-39630}, doi = {10.4230/LIPIcs.STACS.2013.538}, annote = {Keywords: Approximation algorithms, online algorithms, bin packing, First Fit} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Collection of the open problems presented at the scheduling seminar.

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3, author = {Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.}, title = {{10071 Open Problems – Scheduling}}, booktitle = {Scheduling}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10071}, editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3}, URN = {urn:nbn:de:0030-drops-25367}, doi = {10.4230/DagSemProc.10071.3}, annote = {Keywords: Open problems, scheduling} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.

Tomas Ebenlendr and Jiri Sgall. Semi-Online Preemptive Scheduling: One Algorithm for All Variants. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 349-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ebenlendr_et_al:LIPIcs.STACS.2009.1840, author = {Ebenlendr, Tomas and Sgall, Jiri}, title = {{Semi-Online Preemptive Scheduling: One Algorithm for All Variants}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {349--360}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1840}, URN = {urn:nbn:de:0030-drops-18406}, doi = {10.4230/LIPIcs.STACS.2009.1840}, annote = {Keywords: On-line algorithms, Scheduling} }

Document

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

We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques presented cover charging schemes, potential function arguments, and lower bounds based on Yao's principle. The studied problem is equivalent to the following buffer management problem: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The presented algorithms improve upon 2-competitive greedy algorithm, the competitive ratio is 1.939 for deterministic and 1.582 for randomized algorithms.

Jiri Sgall. Online Scheduling. 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{sgall:DagSemProc.05031.20, author = {Sgall, Jiri}, title = {{Online Scheduling}}, 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.20}, URN = {urn:nbn:de:0030-drops-695}, doi = {10.4230/DagSemProc.05031.20}, annote = {Keywords: online algorithms , scheduling} }

Document

**Published in:** LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

The total area of the 24 squares of sizes 1,2,…,24 is equal to the area of the 70× 70 square. Can this equation be demonstrated by a tiling of the 70× 70 square with the 24 squares of sizes 1,2,…,24? The answer is "NO", no such tiling exists. This has been demonstrated by computer search. However, until now, no proof without use of computer was given. We fill this gap and give a complete combinatorial proof.

Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, and Zsolt Tuza. No Tiling of the 70 × 70 Square with Consecutive Squares. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sgall_et_al:LIPIcs.FUN.2024.28, author = {Sgall, Ji\v{r}{\'\i} and Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Hvattum, Lars Magnus and Tuza, Zsolt}, title = {{No Tiling of the 70 × 70 Square with Consecutive Squares}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.28}, URN = {urn:nbn:de:0030-drops-199362}, doi = {10.4230/LIPIcs.FUN.2024.28}, annote = {Keywords: square packing, Gardner’s problem, combinatorial proof} }

Document

APPROX

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

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.

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} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003].
In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances.
We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.ISAAC.2016.21, author = {B\"{o}hm, Martin and Chrobak, Marek and Jez, Lukasz and Li, Fei and Sgall, Jir{\'\i} and Vesel\'{y}, Pavel}, title = {{Online Packet Scheduling with Bounded Delay and Lookahead}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.21}, URN = {urn:nbn:de:0030-drops-67901}, doi = {10.4230/LIPIcs.ISAAC.2016.21}, annote = {Keywords: buffer management, online scheduling, online algorithm, lookahead} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12, author = {Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel}, title = {{Online Algorithms for Multi-Level Aggregation}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.12}, URN = {urn:nbn:de:0030-drops-63637}, doi = {10.4230/LIPIcs.ESA.2016.12}, annote = {Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7.
We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins.
Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins.
Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

György Dósa and Jiri Sgall. First Fit bin packing: A tight analysis. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 538-549, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{dosa_et_al:LIPIcs.STACS.2013.538, author = {D\'{o}sa, Gy\"{o}rgy and Sgall, Jiri}, title = {{First Fit bin packing: A tight analysis}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {538--549}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.538}, URN = {urn:nbn:de:0030-drops-39630}, doi = {10.4230/LIPIcs.STACS.2013.538}, annote = {Keywords: Approximation algorithms, online algorithms, bin packing, First Fit} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Collection of the open problems presented at the scheduling seminar.

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3, author = {Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.}, title = {{10071 Open Problems – Scheduling}}, booktitle = {Scheduling}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10071}, editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3}, URN = {urn:nbn:de:0030-drops-25367}, doi = {10.4230/DagSemProc.10071.3}, annote = {Keywords: Open problems, scheduling} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.

Tomas Ebenlendr and Jiri Sgall. Semi-Online Preemptive Scheduling: One Algorithm for All Variants. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 349-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ebenlendr_et_al:LIPIcs.STACS.2009.1840, author = {Ebenlendr, Tomas and Sgall, Jiri}, title = {{Semi-Online Preemptive Scheduling: One Algorithm for All Variants}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {349--360}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1840}, URN = {urn:nbn:de:0030-drops-18406}, doi = {10.4230/LIPIcs.STACS.2009.1840}, annote = {Keywords: On-line algorithms, Scheduling} }

Document

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

We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques presented cover charging schemes, potential function arguments, and lower bounds based on Yao's principle. The studied problem is equivalent to the following buffer management problem: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The presented algorithms improve upon 2-competitive greedy algorithm, the competitive ratio is 1.939 for deterministic and 1.582 for randomized algorithms.

Jiri Sgall. Online Scheduling. 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{sgall:DagSemProc.05031.20, author = {Sgall, Jiri}, title = {{Online Scheduling}}, 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.20}, URN = {urn:nbn:de:0030-drops-695}, doi = {10.4230/DagSemProc.05031.20}, annote = {Keywords: online algorithms , scheduling} }