Search Results

Documents authored by Jansen, Klaus

Document
DOI: 10.4230/LIPIcs.SEA.2024.13
3/2-Dual Approximation for CPU/GPU Scheduling

Authors: Bernhard Sebastian Germann, Klaus Jansen, Felix Ohnesorge, and Malte Tutas

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
We present a fast and efficient 3/2 dual approximation algorithm for CPU/GPU scheduling under the objective of makespan minimization. In CPU/GPU scheduling tasks can be scheduled on two different architectures. When executed on the CPU, a task is moldable and can be assigned to multiple cores. The running time becomes a function in the assigned cores. On a GPU, the task is a classical job with a set processing time. Both settings have drawn recent independent scientific interest. For the moldable CPU scheduling, the current best known constant rate approximation is a 3/2 approximation algorithm [Wu et al. EJOR volume 306]. The best efficient algorithm for this setting is a 3/2+ε approximation [Mounie et al. SIAM '07] whereas GPU scheduling admits a 13/11 approximation [Coffman, Garey, Johnson SIAM'78]. We improve upon the current best known algorithms for CPU/GPU scheduling by Bleuse et al. by formulating a novel multidimensional multiple choice knapsack to allot tasks to either architecture and schedule them there with known algorithms. This yields an improved running time over the current state of the art. We complement our theoretical results with experimentation that shows a significant speedup by using practical optimizations and explore their efficacy.
Cite as

Bernhard Sebastian Germann, Klaus Jansen, Felix Ohnesorge, and Malte Tutas. 3/2-Dual Approximation for CPU/GPU Scheduling. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{germann_et_al:LIPIcs.SEA.2024.13,
  author =	{Germann, Bernhard Sebastian and Jansen, Klaus and Ohnesorge, Felix and Tutas, Malte},
  title =	{{3/2-Dual Approximation for CPU/GPU Scheduling}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.13},
  URN =		{urn:nbn:de:0030-drops-203782},
  doi =		{10.4230/LIPIcs.SEA.2024.13},
  annote =	{Keywords: computing, machine scheduling, moldable, CPU/GPU}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.13
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Authors: Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett. , 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m⋅log(4mΔ), where m is the number of constraints, and Δ is the largest absolute coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m⋅(log(3A_max)+√{log(A_max)}), where A_max≔ ‖A‖₁ denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m⋅log(1.46 A_max). Our upper bounds also hold with A_max replaced by √mΔ, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||C_{max}). Our EPTAS yields a (1+ε)-approximation for Q||C_{max} on N jobs in time 2^𝒪(1/ε log³(1/ε)log(log(1/ε))) + 𝒪(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^𝒪(1/ε log⁴(1/ε)) + N^𝒪(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||C_max, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.
Cite as

Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm. New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ISAAC.2023.13,
  author =	{Berndt, Sebastian and Brinkop, Hauke and Jansen, Klaus and Mnich, Matthias and Stamm, Tobias},
  title =	{{New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.13},
  URN =		{urn:nbn:de:0030-drops-193155},
  doi =		{10.4230/LIPIcs.ISAAC.2023.13},
  annote =	{Keywords: Integer programming, scheduling algorithms, uniformly related machines, makespan minimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.78
A PTAS for Packing Hypercubes into a Knapsack

Authors: Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study the d-dimensional hypercube knapsack problem ({d}-D Hc-Knapsack) where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+ε). For d = 2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d > 2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren’s result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called 𝒱-Boxes and 𝒩-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.
Cite as

Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas. A PTAS for Packing Hypercubes into a Knapsack. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2022.78,
  author =	{Jansen, Klaus and Khan, Arindam and Lira, Marvin and Sreenivas, K. V. N.},
  title =	{{A PTAS for Packing Hypercubes into a Knapsack}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78},
  URN =		{urn:nbn:de:0030-drops-164192},
  doi =		{10.4230/LIPIcs.ICALP.2022.78},
  annote =	{Keywords: Multidimensional knapsack, geometric packing, cube packing, strip packing}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.21
Peak Demand Minimization via Sliced Strip Packing

Authors: Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas

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

Abstract
We study the Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Nonpreemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5/3+ε)-approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1+ε) OPT. The remaining jobs fit into a thin container of height 1. The previous best result for NPDM was a 2.7 approximation based on FFDH [Ranjan et al., 2015]. One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above.
Cite as

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak Demand Minimization via Sliced Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.APPROX/RANDOM.2021.21,
  author =	{Deppert, Max A. and Jansen, Klaus and Khan, Arindam and Rau, Malin and Tutas, Malte},
  title =	{{Peak Demand Minimization via Sliced Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.21},
  URN =		{urn:nbn:de:0030-drops-147145},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.21},
  annote =	{Keywords: scheduling, peak demand minimization, approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.53
Closing the Gap for Single Resource Constraint Scheduling

Authors: Klaus Jansen and Malin Rau

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In the problem called single resource constraint scheduling, we are given m identical machines and a set of jobs, each needing one machine to be processed as well as a share of a limited renewable resource R. A schedule of these jobs is feasible if, at each point in the schedule, the number of machines and resources required by jobs processed at this time is not exceeded. It is NP-hard to approximate this problem with a ratio better than 3/2. On the other hand, the best algorithm so far has an absolute approximation ratio of 2+ε. In this paper, we present an algorithm with absolute approximation ratio (3/2+ε), which closes the gap between inapproximability and best algorithm with exception of a negligible small ε.
Cite as

Klaus Jansen and Malin Rau. Closing the Gap for Single Resource Constraint Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2021.53,
  author =	{Jansen, Klaus and Rau, Malin},
  title =	{{Closing the Gap for Single Resource Constraint Scheduling}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.53},
  URN =		{urn:nbn:de:0030-drops-146344},
  doi =		{10.4230/LIPIcs.ESA.2021.53},
  annote =	{Keywords: resource constraint scheduling, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.39
Fuzzy Simultaneous Congruences

Authors: Max A. Deppert, Klaus Jansen, and Kim-Manuel Klein

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer s that is specified by n fixed remainders modulo integer divisors a₁,… ,a_n we consider remainder intervals R₁,… ,R_n such that s is feasible if and only if s is congruent to r_i modulo a_i for some remainder r_i in interval R_i for all i. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i.e. a_{i+1}/a_i is an integer for all i < n, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time 𝒪(n²) and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time 𝒪(n³).
Cite as

Max A. Deppert, Klaus Jansen, and Kim-Manuel Klein. Fuzzy Simultaneous Congruences. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.MFCS.2021.39,
  author =	{Deppert, Max A. and Jansen, Klaus and Klein, Kim-Manuel},
  title =	{{Fuzzy Simultaneous Congruences}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.39},
  URN =		{urn:nbn:de:0030-drops-144792},
  doi =		{10.4230/LIPIcs.MFCS.2021.39},
  annote =	{Keywords: Simultaneous congruences, Integer programming, Mixing Set, Real-time scheduling, Diophantine approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.44
A Tight (3/2+ε) Approximation for Skewed Strip Packing

Authors: Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau

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

Abstract
In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis. It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A Tight (3/2+ε) Approximation for Skewed Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2020.44,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ameli, Afrouz Jabal and Jansen, Klaus and Khan, Arindam and Rau, Malin},
  title =	{{A Tight (3/2+\epsilon) Approximation for Skewed Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.44},
  URN =		{urn:nbn:de:0030-drops-126478},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.44},
  annote =	{Keywords: strip packing, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.5
Inapproximability Results for Scheduling with Interval and Resource Restrictions

Authors: Marten Maack and Klaus Jansen

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions. For the case of interval restrictions - where the machines can be totally ordered such that jobs are eligible on consecutive machines - we show that there is no polynomial time approximation scheme (PTAS) unless P=NP. The question of whether a PTAS for this variant exists was stated as an open problem before, and PTAS results for special cases of this variant are known. Furthermore, we consider a variant with resource restriction where the sets of eligible machines are of the following form: There is a fixed number of (renewable) resources, each machine has a capacity, and each job a demand for each resource. A job is eligible on a machine if its demand is at most as big as the capacity of the machine for each resource. For one resource, this problem has been intensively studied under several different names and is known to admit a PTAS, and for two resources the variant with interval restrictions is contained as a special case. Moreover, the version with multiple resources is closely related to makespan minimization on parallel machines with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 ≈ 1.02 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.
Cite as

Marten Maack and Klaus Jansen. Inapproximability Results for Scheduling with Interval and Resource Restrictions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{maack_et_al:LIPIcs.STACS.2020.5,
  author =	{Maack, Marten and Jansen, Klaus},
  title =	{{Inapproximability Results for Scheduling with Interval and Resource Restrictions}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.5},
  URN =		{urn:nbn:de:0030-drops-118663},
  doi =		{10.4230/LIPIcs.STACS.2020.5},
  annote =	{Keywords: Scheduling, Restricted Assignment, Approximation, Inapproximability, PTAS}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.18
Online Bin Covering with Limited Migration

Authors: Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most beta * s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classical problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small epsilon). We therefore resolve the competitiveness of the bin covering problem with migration.
Cite as

Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online Bin Covering with Limited Migration. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ESA.2019.18,
  author =	{Berndt, Sebastian and Epstein, Leah and Jansen, Klaus and Levin, Asaf and Maack, Marten and Rohwedder, Lars},
  title =	{{Online Bin Covering with Limited Migration}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.18},
  URN =		{urn:nbn:de:0030-drops-111391},
  doi =		{10.4230/LIPIcs.ESA.2019.18},
  annote =	{Keywords: online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.62
Closing the Gap for Pseudo-Polynomial Strip Packing

Authors: Klaus Jansen and Malin Rau

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Two-dimensional packing problems are a fundamental class of optimization problems and Strip Packing is one of the most natural and famous among them. Indeed it can be defined in just one sentence: Given a set of rectangular axis parallel items and a strip with bounded width and infinite height, the objective is to find a packing of the items into the strip minimizing the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip. It is known that there is no pseudo-polynomial time algorithm for Strip Packing with a ratio better than 5/4 unless P = NP. The best algorithm so far has a ratio of 4/3 + epsilon. In this paper, we close the gap between inapproximability result and currently known algorithms by presenting an algorithm with approximation ratio 5/4 + epsilon. The algorithm relies on a new structural result which is the main accomplishment of this paper. It states that each optimal solution can be transformed with bounded loss in the objective such that it has one of a polynomial number of different forms thus making the problem tractable by standard techniques, i.e., dynamic programming. To show the conceptual strength of the approach, we extend our result to other problems as well, e.g., Strip Packing with 90 degree rotations and Contiguous Moldable Task Scheduling, and present algorithms with approximation ratio 5/4 + epsilon for these problems as well.
Cite as

Klaus Jansen and Malin Rau. Closing the Gap for Pseudo-Polynomial Strip Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2019.62,
  author =	{Jansen, Klaus and Rau, Malin},
  title =	{{Closing the Gap for Pseudo-Polynomial Strip Packing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.62},
  URN =		{urn:nbn:de:0030-drops-111831},
  doi =		{10.4230/LIPIcs.ESA.2019.62},
  annote =	{Keywords: Strip Packing, pseudo-polynomial, 90 degree rotation, Contiguous Moldable Task Scheduling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.74
Local Search Breaks 1.75 for Graph Balancing

Authors: Klaus Jansen and Lars Rohwedder

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algorithm known achieves an approximation ratio of 1.75 and it is based on rounding a linear program with this exact integrality gap. It is also known that there is no (1.5 - epsilon)-approximation algorithm, unless P=NP. Can we do better than 1.75? We prove that a different LP formulation, the configuration LP, has a strictly smaller integrality gap. Graph Balancing was the last one in a group of related problems from literature, for which it was open whether the configuration LP is stronger than previous, simple LP relaxations. We base our proof on a local search approach that has been applied successfully to the more general Restricted Assignment problem, which in turn is a prominent special case of makespan minimization on unrelated machines. With a number of technical novelties we are able to obtain a bound of 1.749 for the case of Graph Balancing. It is not clear whether the local search algorithm we present terminates in polynomial time, which means that the bound is non-constructive. However, it is a strong evidence that a better approximation algorithm is possible using the configuration LP and it allows the optimum to be estimated within a factor better than 1.75. A particularly interesting aspect of our techniques is the way we handle small edges in the local search. We manage to exploit the configuration constraints enforced on small edges in the LP. This may be of interest to other problems such as Restricted Assignment as well.
Cite as

Klaus Jansen and Lars Rohwedder. Local Search Breaks 1.75 for Graph Balancing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.74,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{Local Search Breaks 1.75 for Graph Balancing}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.74},
  URN =		{urn:nbn:de:0030-drops-106501},
  doi =		{10.4230/LIPIcs.ICALP.2019.74},
  annote =	{Keywords: graph, approximation algorithm, scheduling, integrality gap, local search}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.75
Near-Linear Time Algorithm for n-fold ILPs via Color Coding

Authors: Klaus Jansen, Alexandra Lassota, and Lars Rohwedder

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study an important case of ILPs max {c^Tx | Ax = b, l <= x <= u, x in Z^{n t}} with n * t variables and lower and upper bounds l, u in Z^{nt}. In n-fold ILPs non-zero entries only appear in the first r rows of the matrix A and in small blocks of size s x t along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that n-fold ILPs can be solved in FPT time regarding the parameters s, r, and Delta, where Delta is the greatest absolute value of an entry in A. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time Omega(n), leading to a quadratic running time in n. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for n-fold ILPs with a running time that is near-linear in the number nt of variables, namely (rs Delta)^{O(r^2s + s^2)} L^2 * nt log^{O(1)}(nt), where L is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of L.
Cite as

Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. Near-Linear Time Algorithm for n-fold ILPs via Color Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.75,
  author =	{Jansen, Klaus and Lassota, Alexandra and Rohwedder, Lars},
  title =	{{Near-Linear Time Algorithm for n-fold ILPs via Color Coding}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{75:1--75:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.75},
  URN =		{urn:nbn:de:0030-drops-106518},
  doi =		{10.4230/LIPIcs.ICALP.2019.75},
  annote =	{Keywords: Near-Linear Time Algorithm, n-fold ILP, Color Coding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.43
On Integer Programming and Convolution

Authors: Klaus Jansen and Lars Rohwedder

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Integer programs with a constant number of constraints are solvable in pseudo-polynomial time. We give a new algorithm with a better pseudo-polynomial running time than previous results. Moreover, we establish a strong connection to the problem (min, +)-convolution. (min, +)-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number of constraints are equivalent to improvements for (min, +)-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints and for this we also give a tight lower bound, which is based on the SETH.
Cite as

Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ITCS.2019.43,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{On Integer Programming and Convolution}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.43},
  URN =		{urn:nbn:de:0030-drops-101365},
  doi =		{10.4230/LIPIcs.ITCS.2019.43},
  annote =	{Keywords: Integer programming, convolution, dynamic programming, SETH}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.44
Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times

Authors: Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently. As an application, we consider scheduling problems with setup times, in which a set of jobs has to be scheduled on a set of identical machines, with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time f(1/epsilon) x poly(|I|) with a single exponential term in f for the first and a double exponential one for the second case. Previously, only constant factor approximations of 5/3 and 4/3 + epsilon respectively were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine.
Cite as

Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ITCS.2019.44,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Maack, Marten and Rau, Malin},
  title =	{{Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.44},
  URN =		{urn:nbn:de:0030-drops-101375},
  doi =		{10.4230/LIPIcs.ITCS.2019.44},
  annote =	{Keywords: Parallel Machines, Setup Time, EPTAS, n-fold integer programming}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018
LIPIcs, Volume 116, APPROX/RANDOM'18, Complete Volume

Authors: Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer

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

Abstract
LIPIcs, Volume 116, APPROX/RANDOM'18, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{blais_et_al:LIPIcs.APPROX-RANDOM.2018,
  title =	{{LIPIcs, Volume 116, APPROX/RANDOM'18, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018},
  URN =		{urn:nbn:de:0030-drops-97254},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blais_et_al:LIPIcs.APPROX-RANDOM.2018.0,
  author =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.0},
  URN =		{urn:nbn:de:0030-drops-94043},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.SOSA.2018.11
Compact LP Relaxations for Allocation Problems

Authors: Klaus Jansen and Lars Rohwedder

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract
We consider the restricted versions of Scheduling on Unrelated Machines and the Santa Claus problem. In these problems we are given a set of jobs and a set of machines. Every job j has a size p_j and a set of allowed machines \Gamma(j), i.e., it can only be assigned to those machines. In the first problem, the objective is to minimize the maximum load among all machines; in the latter problem it is to maximize the minimum load. For these problems, the strongest LP relaxation known is the configuration LP. The configuration LP has an exponential number of variables and it cannot be solved exactly unless P = NP. Our main result is a new LP relaxation for these problems. This LP has only O(n^3) variables and constraints. It is a further relaxation of the configuration LP, but it obeys the best bounds known for its integrality gap (11/6 and 4). For the configuration LP these bounds were obtained using two local search algorithm. These algorithms, however, differ significantly in presentation. In this paper, we give a meta algorithm based on the local search ideas. With an instantiation for each objective function, we prove the bounds for the new compact LP relaxation (in particular, for the configuration LP). This way, we bring out many analogies between the two proofs, which were not apparent before.
Cite as

Klaus Jansen and Lars Rohwedder. Compact LP Relaxations for Allocation Problems. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:OASIcs.SOSA.2018.11,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{Compact LP Relaxations for Allocation Problems}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{11:1--11:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.11},
  URN =		{urn:nbn:de:0030-drops-83012},
  doi =		{10.4230/OASIcs.SOSA.2018.11},
  annote =	{Keywords: Linear programming, unrelated machines, makespan, max-min, restricted assignment, santa claus}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017
LIPIcs, Volume 81, APPROX/RANDOM'17, Complete Volume

Authors: Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala

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

Abstract
LIPIcs, Volume 81, APPROX/RANDOM'17, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2017,
  title =	{{LIPIcs, Volume 81, APPROX/RANDOM'17, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017},
  URN =		{urn:nbn:de:0030-drops-77101},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017},
  annote =	{Keywords: Network Architecture and Design, Coding and Information Theory, Error Control Codes, Modes of Computation: Online computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Numerical Algorithms and Problems, Nonnumerical Algorithms and Problems}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.0
Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors

Authors: Klaus Jansen, José D. P. Rolim, David P. Williamson, and Santosh S. Vempala

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

Abstract
Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, p. 0:i, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2017.0,
  author =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  title =	{{Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{0:i--0:i},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.0},
  URN =		{urn:nbn:de:0030-drops-75493},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.0},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.13
Online Strip Packing with Polynomial Migration

Authors: Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig

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

Abstract
We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.
Cite as

Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig. Online Strip Packing with Polynomial Migration. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2017.13,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Kosche, Maria and Ladewig, Leon},
  title =	{{Online Strip Packing with Polynomial Migration}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.13},
  URN =		{urn:nbn:de:0030-drops-75620},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.13},
  annote =	{Keywords: strip packing, bin packing, online algorithms, migration factor}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016
LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume

Authors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans

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

Abstract
LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016,
  title =	{{LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016},
  URN =		{urn:nbn:de:0030-drops-66809},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016},
  annote =	{Keywords: Theory of Computation, Models of Computation, Modes of Computation – Online Computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Numerical Algorithms and Problems – Computations on Matrices, Nonnumerical Algorithms and Problems}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.0
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors

Authors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans

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

Abstract
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016.0,
  author =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  title =	{{Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.0},
  URN =		{urn:nbn:de:0030-drops-66235},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.72
Closing the Gap for Makespan Scheduling via Sparsification Techniques

Authors: Klaus Jansen, Kim-Manuel Klein, and José Verschae

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

Abstract
Makespan scheduling on identical machines is one of the most basic and fundamental packing problem studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NPhard, and thus we do not expect a (1 + epsilon)-approximation algorithm with a running time that depends polynomially on 1/epsilon. Furthermore, Chen et al. [Chen/JansenZhang, SODA'13] recently showed that a running time of 2^{1/epsilon}^{1-delta} + poly(n) for any delta > 0 would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on 1/epsilon, the better of which achieves a running time of 2^{~O(1/epsilon^{2})} + O(n*log(n)) [Jansen, SIAM J. Disc. Math. 2010]. In this paper we obtain an algorithm with a running time of 2^{~O(1/epsilon)} + O(n*log(n)), which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time 2^{~O(1/epsilon)} + poly(n).
Cite as

Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2016.72,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Verschae, Jos\'{e}},
  title =	{{Closing the Gap for Makespan Scheduling via Sparsification Techniques}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{72:1--72:13},
  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.72},
  URN =		{urn:nbn:de:0030-drops-62122},
  doi =		{10.4230/LIPIcs.ICALP.2016.72},
  annote =	{Keywords: scheduling, approximation, PTAS, makespan, ETH}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.24
Estimating The Makespan of The Two-Valued Restricted Assignment Problem

Authors: Klaus Jansen, Kati Land, and Marten Maack

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We consider a special case of the scheduling problem on unrelated machines, namely the Restricted Assignment Problem with two different processing times. We show that the configuration LP has an integrality gap of at most 5/3 ~ 1.667 for this problem. This allows us to estimate the optimal makespan within a factor of 5/3, improving upon the previously best known estimation algorithm with ratio 11/6 ~ 1.833 due to Chakrabarty, Khanna, and Li.
Cite as

Klaus Jansen, Kati Land, and Marten Maack. Estimating The Makespan of The Two-Valued Restricted Assignment Problem. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SWAT.2016.24,
  author =	{Jansen, Klaus and Land, Kati and Maack, Marten},
  title =	{{Estimating The Makespan of The Two-Valued Restricted Assignment Problem}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.24},
  URN =		{urn:nbn:de:0030-drops-60467},
  doi =		{10.4230/LIPIcs.SWAT.2016.24},
  annote =	{Keywords: unrelated scheduling, restricted assignment, configuration LP, integrality gap, estimation algorithm}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.42
Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows

Authors: Niklas Paulsen, Florian Diedrich, and Klaus Jansen

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
We present heuristics to handle practical travelling salesman problems with multiple time windows per node, where the optimization goal is minimal tour duration, which is the time spent outside the depot node. We propose a dynamic programming approach which combines state labels by encoding intervals to handle the larger state space needed for this objective function. Our implementation is able to solve many practical instances in real-time and is used for heuristic search of near-optimal solutions for hard instances. In addition, we outline a hybrid genetic algorithm we implemented to cope with hard or unknown instances. Experimental evaluation proves the efficiency and suitability for practical use of our algorithms and even leads to improved upper bounds for yet unsolved instances from the literature.
Cite as

Niklas Paulsen, Florian Diedrich, and Klaus Jansen. Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 42-55, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{paulsen_et_al:OASIcs.ATMOS.2015.42,
  author =	{Paulsen, Niklas and Diedrich, Florian and Jansen, Klaus},
  title =	{{Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{42--55},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.42},
  URN =		{urn:nbn:de:0030-drops-54608},
  doi =		{10.4230/OASIcs.ATMOS.2015.42},
  annote =	{Keywords: TSPTW, minimum tour duration, dynamic programming, heuristics}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015
LIPIcs, Volume 40, APPROX/RANDOM'15, Complete Volume

Authors: Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim

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

Abstract
LIPIcs, Volume 40, APPROX/RANDOM'15, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{garg_et_al:LIPIcs.APPROX-RANDOM.2015,
  title =	{{LIPIcs, Volume 40, APPROX/RANDOM'15, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015},
  URN =		{urn:nbn:de:0030-drops-54012},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015},
  annote =	{Keywords: Data Structures, Coding and Information Theory, Theory of Computation, Computation by Abstract Devices, Modes of Computation, Complexity Measures and Problem Complexity, Numerical Algorithms and Problems, Nonnumerical Algorithms and Problems, Approximation, Numerical Linear Algorithms and Problems}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.i
Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors

Authors: Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim

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

Abstract
Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. i-xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX-RANDOM.2015.i,
  author =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  title =	{{Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{i--xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.i},
  URN =		{urn:nbn:de:0030-drops-53474},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.135
Fully Dynamic Bin Packing Revisited

Authors: Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein

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

Abstract
We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).
Cite as

Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully Dynamic Bin Packing Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 135-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.APPROX-RANDOM.2015.135,
  author =	{Berndt, Sebastian and Jansen, Klaus and Klein, Kim-Manuel},
  title =	{{Fully Dynamic Bin Packing Revisited}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{135--151},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.135},
  URN =		{urn:nbn:de:0030-drops-53008},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.135},
  annote =	{Keywords: online, bin packing, migration factor, robust, AFPTAS}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014
LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume

Authors: Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore

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

Abstract
LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2014,
  title =	{{LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014},
  URN =		{urn:nbn:de:0030-drops-47603},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014},
  annote =	{Keywords: Network Architecture and Design, Computer-communication, Coding and Information Theory, Theory of Computation, Computation by Abstract Devices, Models of Computation – relations between models, Modes of Computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Klaus Jansen, José Rolim, Nikhil R. Devanur, and Cristopher Moore

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

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. i-xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2014.i,
  author =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{i--xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.i},
  URN =		{urn:nbn:de:0030-drops-46846},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/DagRep.1.2.67
Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091)

Authors: Klaus Jansen, Claire Matieu, Hadas Shachnai, and Neal E. Young

Published in: Dagstuhl Reports, Volume 1, Issue 2 (2011)

Abstract
From 27.02.2011 to 4.03.2011, the Dagstuhl Seminar 11091 ``Packing and Scheduling Algorithms for Information and Communication Services'' was held in Schloss Dagstuhl Leibniz Center for Informatics. During the seminar, several participants presented their current research, and on-going work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Klaus Jansen, Claire Matieu, Hadas Shachnai, and Neal E. Young. Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091). In Dagstuhl Reports, Volume 1, Issue 2, pp. 67-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{jansen_et_al:DagRep.1.2.67,
  author =	{Jansen, Klaus and Matieu, Claire and Shachnai, Hadas and Young, Neal E.},
  title =	{{Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091)}},
  pages =	{67--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{2},
  editor =	{Jansen, Klaus and Matieu, Claire and Shachnai, Hadas and Young, Neal E.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.2.67},
  URN =		{urn:nbn:de:0030-drops-31579},
  doi =		{10.4230/DagRep.1.2.67},
  annote =	{Keywords: Packing, scheduling, information and communication services, combinatorial optimization, mathematical programming, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1350
Trimming of Graphs, with Application to Point Labeling

Authors: Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is trimmable if for each constant $t>0$, there is a constant $g=g(t)$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. Based on this result, we derive a polynomial-time approximation scheme for the problem of labeling weighted points with nonoverlapping sliding labels of unit height and given lengths so as to maximize the total weight of the labeled points. This settles one of the last major open questions in the theory of map labeling.
Cite as

Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. Trimming of Graphs, with Application to Point Labeling. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 265-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.STACS.2008.1350,
  author =	{Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander},
  title =	{{Trimming of Graphs, with Application to Point Labeling}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{265--276},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1350},
  URN =		{urn:nbn:de:0030-drops-13509},
  doi =		{10.4230/LIPIcs.STACS.2008.1350},
  annote =	{Keywords: Trimming weighted graphs, domino treewidth, planar graphs, point-feature label placement, map labeling, polynomial-time approximation schemes}
}
Document
DOI: 10.4230/DagSemProc.07211.1
07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes

Authors: Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)

Abstract
From May 20 to May 25, 2007, the Dagstuhl Seminar 07211 ``Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad. 07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.07211.1,
  author =	{Brandst\"{a}dt, Andreas and Jansen, Klaus and Kratsch, Dieter and Spinrad, Jeremy P.},
  title =	{{07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.1},
  URN =		{urn:nbn:de:0030-drops-12697},
  doi =		{10.4230/DagSemProc.07211.1},
  annote =	{Keywords: Graph theory, approximation algorithms, certifying algorithms, exact algorithms}
}
Document
DOI: 10.4230/DagSemProc.04221.1
04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes

Authors: Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Proceedings, Volume 4221, Robust and Approximative Algorithms an Particular Graph Classes (2005)

Abstract
From 23.05.04 to 28.05.04, the Dagstuhl Seminar 04221 ``Robust and Approximative Algorithms on Particular Graph Classes'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, and Jeremy P. Spinrad. 04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes. In Robust and Approximative Algorithms an Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 4221, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.04221.1,
  author =	{Brandst\"{a}dt, Andreas and Corneil, Derek G. and Jansen, Klaus and Spinrad, Jeremy P.},
  title =	{{04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes}},
  booktitle =	{Robust and Approximative Algorithms an Particular Graph Classes},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4221},
  editor =	{Andreas Brandst\"{a}dt and Derek G. Corneil and Klaus Jansen and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04221.1},
  URN =		{urn:nbn:de:0030-drops-2732},
  doi =		{10.4230/DagSemProc.04221.1},
  annote =	{Keywords: Graph algorithms, graph classes, graph algorithms, robust algorithms, approximation}
}
Document
DOI: 10.4230/DagSemRep.345
Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)

Authors: Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong. Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251). Dagstuhl Seminar Report 345, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{bampis_et_al:DagSemRep.345,
  author =	{Bampis, Evripidis and Jansen, Klaus and Persiano, Giuseppe and Solis-Oba, Roberto and Wilfong, Gordon T.},
  title =	{{Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{345},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.345},
  URN =		{urn:nbn:de:0030-drops-152265},
  doi =		{10.4230/DagSemRep.345},
}
Document
DOI: 10.4230/DagSemRep.263
Linear, Semidefinite Programming and Randomization Methods for Combinatorial Optimization Problems (Dagstuhl Seminar 00041)

Authors: Klaus Jansen, Jose Rolim, and Madhu Sudan

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Klaus Jansen, Jose Rolim, and Madhu Sudan. Linear, Semidefinite Programming and Randomization Methods for Combinatorial Optimization Problems (Dagstuhl Seminar 00041). Dagstuhl Seminar Report 263, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{jansen_et_al:DagSemRep.263,
  author =	{Jansen, Klaus and Rolim, Jose and Sudan, Madhu},
  title =	{{Linear, Semidefinite Programming and Randomization Methods for Combinatorial Optimization Problems (Dagstuhl Seminar 00041)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{263},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.263},
  URN =		{urn:nbn:de:0030-drops-151486},
  doi =		{10.4230/DagSemRep.263},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact