- Quantum Computing for Discrete Optimization: A Highlight of Three Technologies (Alexey Bochkarev, Raoul Heese, Sven Jäger, Philine Schiewe, and Anita Schöbel)
European Journal of Operational Research, 329(3):747–766, 2026.
@article{BochkarevHeeseJaegerSchieweSchoebel,
archiveprefix = {arXiv},
author = {Alexey Bochkarev and Raoul Heese and Sven Jäger and Philine Schiewe and Anita Schöbel},
doi = {10.1016/j.ejor.2025.07.063},
arxiv = {2409.01373},
primaryclass = {math.OC},
title = {Quantum Computing for Discrete Optimization: A Highlight of Three Technologies},
year = {2026},
month = {mar},
volume = {329},
number = {3},
pages = {747--766},
journal = {European Journal of Operational Research},
}
Quantum optimization has emerged as a promising frontier of quantum computing, providing novel numerical approaches to mathematical optimization problems. The main goal of this paper is to facilitate interdisciplinary research between the Operations Research (OR) and Quantum Computing communities by providing an OR scientist's perspective on selected quantum-powered methods for discrete optimization. To this end, we consider three quantum-powered optimization approaches that make use of different types of quantum hardware available on the market. To illustrate these approaches, we solve three classical optimization problems: the Traveling Salesperson Problem, Weighted Maximum Cut, and Maximum Independent Set. With a general OR audience in mind, we attempt to provide an intuition behind each approach along with key references, describe the corresponding high-level workflow, and highlight crucial practical considerations. In particular, we emphasize the importance of problem formulations and device-specific configurations, and their impact on the amount of resources required for computation (where we focus on the number of qubits). These points are illustrated with a series of experiments on three types of quantum computers: a neutral atom machine from QuEra, a quantum annealer from D-Wave, and a gate-based device from IBM.
- Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling (Sven Jäger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt, and Philipp Warode)
Mathematical Programming, 210:457–509, 2025.
@article{JaegerSagnolSchmidtgenanntWaldschmidtWarode2025,
author = {Jäger, Sven and Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Warode, Philipp},
journal = {Mathematical Programming},
title = {Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling},
year = {2025},
month = {mar},
pages = {457--509},
volume = {210},
archiveprefix = {arXiv},
doi = {10.1007/s10107-024-02118-8},
arxiv = {2211.02044},
extrabuttonlink = {kill-and-restart.html},
primaryclass = {cs.DS},
}
We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of $3$ for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any $𝑏 > 1$ a tight analysis for the natural $𝑏$-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of $(1+3\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 3.032$ for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is $2$-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than $10$ for adaptions of the $𝑏$-scaling strategy to online release dates and unweighted jobs on identical parallel machines.
- The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints (Sven Jäger, Alexander Lindermayr, and Nicole Megow)
SODA 2025 – Proc. 36th ACM-SIAM Symposium on Discrete Algorithms, pp. 3901–3930.
@inproceedings{JaegerLindermayrMegow2025,
author = {Sven Jäger and Alexander Lindermayr and Nicole Megow},
booktitle = {SODA 2025 – Proc. 36th ACM-SIAM Symposium on Discrete Algorithms},
title = {The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints},
year = {2025},
editor = {Yossi Azar and Debmalya Panigrahi},
month = {jan},
pages = {3901--3930},
archiveprefix = {arXiv},
doi = {10.1137/1.9781611978322.132},
arxiv = {2408.14310},
eventdate = {2025-01-12/2025-01-15},
eventtitle = {ACM-SIAM Symposium on Discrete Algorithms},
primaryclass = {cs.DS},
venue = {New Orleans, LA, USA},
}
The Polytope Scheduling Problem (PSP) was introduced by Im, Kulkarni, and Munagala (JACM 2018) as a very general abstraction of resource allocation over time and captures many well-studied problems including classical unrelated machine scheduling, multidimensional scheduling, and broadcast scheduling. In PSP, jobs with different arrival times receive processing rates that are subject to arbitrary packing constraints. An elegant and well-known algorithm for instantaneous rate allocation with good fairness and efficiency properties is the Proportional Fairness algorithm (PF), which was analyzed for PSP by Im et al. We drastically improve the analysis of the PF algorithm for both the general PSP and several of its important special cases subject to the objective of minimizing the sum of weighted completion times. We reduce the upper bound on the competitive ratio from 128 to 27 for general PSP and to 4 for the prominent class of monotone PSP. For certain heterogeneous machine environments we even close the substantial gap to the lower bound of 2 for non-clairvoyant scheduling. Our analysis also gives the first polynomial-time improvements over the nearly 30-year-old bounds on the competitive ratio of the doubling framework by Hall, Shmoys, and Wein (SODA 1996) for clairvoyant online preemptive scheduling on unrelated machines. Somewhat surprisingly, we achieve this improvement by a non-clairvoyant algorithm, thereby demonstrating that non-clairvoyance is not a (significant) hurdle. Our improvements are based on exploiting monotonicity properties of PSP, providing tight dual fitting arguments on structured instances, and showing new additivity properties on the optimal objective value for scheduling on unrelated machines. Finally, we establish new connections of PF to matching markets, and thereby provide new insights on equilibria and their computational complexity.
- Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs (Sven Jäger and Philipp Warode)
SOSA 2024 – SIAM Symposium on Simplicity in Algorithms, pp. 82–96.
@inproceedings{JaegerWarode2024,
author = {Sven Jäger and Philipp Warode},
booktitle = {SOSA 2024 – SIAM Symposium on Simplicity in Algorithms},
title = {Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs},
year = {2024},
editor = {Merav Parter and Seth Pettie},
month = {jan},
pages = {82--96},
archiveprefix = {arXiv},
doi = {10.1137/1.9781611977936.8},
arxiv = {2309.12031},
eventdate = {2024-01-08/2024-01-10},
eventtitle = {SIAM Symposium on Simplicity in Algorithms},
primaryclass = {cs.DS},
venue = {Alexandria, VA, USA},
}
We consider the precedence-constrained scheduling problem to minimize the total weighted completion time. For a single machine, several 2-approximation algorithms are known, which are based on linear programming and network flows. We show that the same ratio is achieved by a simple weighted round-robin rule. Moreover, for preemptive scheduling on identical parallel machines, we give a strongly polynomial 3-approximation, which computes processing rates by solving a sequence of parametric flow problems. This matches the best known constant performance guarantee, previously attained only by a weakly polynomial LP-based algorithm. Our algorithms are both applicable in non-clairvoyant scheduling, where processing times are initially unknown. In this setting, our performance guarantees improve upon the best competitive ratio of 8 known so far.
- Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities (Tobias Harks, Sven Jäger, Michael Markl, and Philine Schiewe)
ATMOS 2024 – Proc. 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 17:1–17:17.
@inproceedings{HarksJaegerMarklSchiewe2024,
author = {Tobias Harks and Sven Jäger and Michael Markl and Philine Schiewe},
booktitle = {ATMOS 2024 – Proc. 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
title = {Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities},
year = {2024},
month = {sep},
number = {123},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
series = {OASIcs},
archiveprefix = {arXiv},
doi = {10.4230/OASIcs.ATMOS.2024.17},
pages = {17:1--17:17},
arxiv = {2406.17153},
eventdate = {2024-09-05/2024-09-06},
eventtitle = {Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
primaryclass = {cs.GT},
venue = {Egham, UK},
}
Modelling passenger assignments in public transport networks is a fundamental task for city planners, especially when deliberating network infrastructure decisions. A key aspect of a realistic model for passenger assignments is to integrate selfish routing behaviour of passengers on the one hand, and the limited vehicle capacities on the other hand. We formulate a side-constrained user equilibrium model in a schedule-based time-expanded transit network, where passengers are modelled via a continuum of non-atomic agents that want to travel with a fixed start time from a user-specific origin to a destination. An agent's route may comprise several rides along given lines, each using vehicles with hard loading capacities. We give a characterization of (side-constrained) user equilibria via a quasi-variational inequality and prove their existence by generalizing a well-known existence result of Bernstein and Smith (Transp. Sci., 1994). We further derive a polynomial time algorithm for single-commodity instances and an exact finite time algorithm for the multi-commodity case. Based on our quasi-variational characterization, we finally devise a fast heuristic computing user equilibria, which is tested on real-world instances based on data gained from the Hamburg S-Bahn system and the Swiss long-distance train network. It turns out that w.r.t. the total travel time, the computed user-equilibria are quite efficient compared to a system optimum, which neglects equilibrium constraints and only minimizes total travel time.
- Periodic Timetabling: Travel Time vs. Regenerative Energy (Sven Jäger, Sarah Roth, and Anita Schöbel)
ATMOS 2024 – Proc. 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 10:1–10:20.
@inproceedings{JaegerRothSchoebel2024,
author = {Sven Jäger and Sarah Roth and Anita Schöbel},
booktitle = {ATMOS 2024 – Proc. 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
title = {Periodic Timetabling: Travel Time vs. Regenerative Energy},
year = {2024},
month = {sep},
number = {123},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
series = {OASIcs},
doi = {10.4230/OASIcs.ATMOS.2024.10},
pages = {10:1--10:20},
eventdate = {2024-09-05/2024-09-06},
eventtitle = {Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
venue = {Egham, UK},
}
While it is important to provide attractive public transportation to the passengers allowing short travel times, it should also be a major concern to reduce the amount of energy used by the public transport system. Electrical trains can regenerate energy when braking, which can be used by a nearby accelerating train. Therefore, apart from the minimization of travel times, the maximization of brake-traction overlaps of nearby trains is an important objective in periodic timetabling. Recently, this has been studied in a model allowing small modifications of a nominal timetable. We investigate the problem of finding periodic timetables that are globally good in both objective functions. We show that the general problem is NP-hard, even restricted to a single transfer station and if only travel time is to be minimized, and give an algorithm with an additive error bound for maximizing the brake-traction overlap on this small network. Moreover, we identify special cases in which the problem is solvable in polynomial time. Finally, we demonstrate the trade-off between the two objective functions in an experimental study.
- An optimization case study for solving a transport robot scheduling problem on quantum-hybrid and quantum-inspired hardware (Dominik Leib, Tobias Seidel, Sven Jäger, Raoul Heese, Caitlin Jones, Abhishek Awasthi, Astrid Niederle, and Michael Bortz)
Scientific Reports, 13:18743, 2023.
@article{LeibSeidelJaegerHeeseJonesAwasthiNiederleBortz2023,
author = {Dominik Leib and Tobias Seidel and Sven Jäger and Raoul Heese and Caitlin Jones and Abhishek Awasthi and Astrid Niederle and Michael Bortz},
journal = {Scientific Reports},
title = {An optimization case study for solving a transport robot scheduling problem on quantum-hybrid and quantum-inspired hardware},
year = {2023},
month = {oct},
volume = {13},
archiveprefix = {arXiv},
doi = {10.1038/s41598-023-45668-1},
pages = {18743},
arxiv = {2309.09736},
primaryclass = {quant-ph},
}
We present a comprehensive case study comparing the performance of D-Waves' quantum-classical hybrid framework, Fujitsu's quantum-inspired digital annealer, and Gurobi's state-of-the-art classical solver in solving a transport robot scheduling problem. This problem originates from an industrially relevant real-world scenario. We provide three different models for our problem following different design philosophies. In our benchmark, we focus on the solution quality and end-to-end runtime of different model and solver combinations. We find promising results for the digital annealer and some opportunities for the hybrid quantum annealer in direct comparison with Gurobi. Our study provides insights into the workflow for solving an application-oriented optimization problem with different strategies, and can be useful for evaluating the strengths and weaknesses of different approaches.
- An improved greedy algorithm for stochastic online scheduling on unrelated machines (Sven Jäger)
Discrete Optimization, Elsevier BV, 47:100753, 2023.
@article{Jaeger2023,
author = {Sven Jäger},
journal = {Discrete Optimization},
title = {An improved greedy algorithm for stochastic online scheduling on unrelated machines},
year = {2023},
issn = {1572-5286},
month = {feb},
volume = {47},
archiveprefix = {arXiv},
doi = {10.1016/j.disopt.2022.100753},
pages = {100753},
arxiv = {2208.06815},
keywords = {Online scheduling, Stochastic scheduling, Total weighted completion time, Unrelated machines},
primaryclass = {cs.DS},
publisher = {Elsevier {BV}},
}
Most practical scheduling applications involve some uncertainty about the arriving times and lengths of the jobs. Stochastic online scheduling is a well-established model capturing this. Here the arrivals occur online, while the processing times are random. For this model, Gupta, Moseley, Uetz, and Xie recently devised an efficient policy for non-preemptive scheduling on unrelated machines with the objective to minimize the expected total weighted completion time. We improve upon this policy by adroitly combining greedy job assignment with $𝛼_j$-point scheduling on each machine. In this way we obtain a $(3+ \sqrt 5)(2 + 𝛥)$-competitive deterministic and an $(8 + 4 𝛥)$-competitive randomized stochastic online scheduling policy, where $𝛥$ is an upper bound on the squared coefficients of variation of the processing times. We also give constant performance guarantees for these policies within the class of all fixed-assignment policies. The $𝛼_j$-point scheduling on a single machine can be enhanced when the upper bound $𝛥$ is known a priori or the processing times are known to be $𝛿$-NBUE for some $𝛿 \geq 1$. This implies improved competitive ratios for unrelated machines but may also be of independent interest.
- Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling (Sven Jäger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt, and Philipp Warode)
IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization, Springer International Publishing, pp. 246–260.
@inproceedings{JaegerSagnolSchmidtgenanntWaldschmidtWarode2023,
author = {Jäger, Sven and Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Warode, Philipp},
booktitle = {IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization},
title = {Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling},
year = {2023},
editor = {Del Pia, Alberto and Kaibel, Volker},
month = {may},
number = {13904},
pages = {246--260},
publisher = {Springer International Publishing},
series = {LNCS},
booksubtitle = {24th International Conference},
doi = {10.1007/978-3-031-32726-1_18},
eventdate = {2023-06-21/2023-06-23},
eventtitle = {Conference on Integer Programming and Combinatorial Optimization},
isbn = {978-3-031-32726-1},
venue = {Madison, WI, USA},
}
We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of $3$ for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any $𝑏 > 1$ a tight analysis for the natural $𝑏$-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of $(1+3\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 3.032$ for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is $2$-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than $10$ for adaptions of the $𝑏$-scaling strategy to online release dates and unweighted jobs on identical parallel machines.
- Scheduling Unrelated Parallel Machines with Attribute-Dependent Setup Times: A Case Study (Sven Jäger, Neele Leithäuser, Sebastian Velten, and Christian Weiß)
Operations Research Proceedings 2022, Springer International Publishing, pp. 581–588.
@inproceedings{JaegerLeithaeuserVeltenWeiss2023,
author = {Sven Jäger and Neele Leithäuser and Sebastian Velten and Christian Weiß},
booktitle = {Operations Research Proceedings 2022},
title = {Scheduling Unrelated Parallel Machines with Attribute-Dependent Setup Times: A Case Study},
year = {2023},
editor = {Grothe, Oliver and Nickel, Stefan and Rebennack, Steffen and Stein, Oliver},
month = {aug},
pages = {581--588},
publisher = {Springer International Publishing},
series = {LNOR},
doi = {10.1007/978-3-031-24907-5_69},
eventtitle = {Operations Research},
venue = {Karlsruhe, Germany},
}
We study a practical production planning problem that was encountered by an industrial partner. Mathematically, the problem can be described as an unrelated parallel machine scheduling problem with deadlines and sequence-dependent setup times. The setup times depend on certain job attributes (e.g. material, color, size) of the successive products. For all products, dated demands are given that must be met with the means of one or multiple production orders that can be assigned to a set of eligible machines. We describe and evaluate different approaches to solve the scheduling problem. Our final algorithm is a combination of an iterated greedy construction heuristic together with a constraint program to locally improve the solution found by the heuristic. For most of our test instances, our algorithm achieves more than 20% reduction of setup times compared to the original solutions used by our industrial partner.
- Gray codes and symmetric chains (Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille)
Journal of Combinatorial Theory, Series B, Elsevier BV, 153:31–60, 2022.
@article{GregorJaegerMuetze+2022,
author = {Petr Gregor and Sven Jäger and Torsten Mütze and Joe Sawada and Kaja Wille},
journal = {Journal of Combinatorial Theory, Series B},
title = {Gray codes and symmetric chains},
year = {2022},
issn = {0095-8956},
month = {mar},
pages = {31--60},
volume = {153},
archiveprefix = {arXiv},
doi = {10.1016/j.jctb.2021.10.008},
arxiv = {1802.06021},
keywords = {Gray code, Hamilton cycle, Hypercube, Poset, Symmetric chain},
primaryclass = {math.CO},
publisher = {Elsevier {BV}},
}
We consider the problem of constructing a cyclic listing of all bitstrings of length $2n+1$ with Hamming weights in the interval $[n+1-\ell , n+\ell ]$, where $1 \leq \ell \leq n+1$, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (the case $\ell = 1$). We provide a solution for the case $\ell = 2$, and we solve a relaxed version of the problem for general values of $\ell$, by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube. The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets. We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the $n$-dimensional hypercube for any $n \geq 12$.
- On orthogonal symmetric chain decompositions (Karl Däubel, Sven Jäger, Torsten Mütze, and Manfred Scheucher)
Electronic Journal of Combinatorics, 26(3):P3.64, 2019.
@article{DaeubelJaegerMuetzeScheucher2019b,
author = {D{\"a}ubel, Karl and J{\"a}ger, Sven and M{\"u}tze, Torsten and Scheucher, Manfred},
journal = {Electronic Journal of Combinatorics},
title = {On orthogonal symmetric chain decompositions},
year = {2019},
issn = {1077-8926},
month = {sep},
number = {3},
volume = {26},
archiveprefix = {arXiv},
doi = {10.37236/8531},
pages = {P3.64},
arxiv = {1810.09847},
pagetotal = {32},
primaryclass = {math.CO},
}
The $n$-cube is the poset obtained by ordering all subsets of $\{1,\dotsc,𝑛\}$ by inclusion, and it can be partitioned into $\binom{𝑛}{\lfloor 𝑛/2 \rfloor}$ chains, which is the minimum possible number. Two such decompositions of the $n$-cube are called orthogonal if any two chains of the decompositions share at most a single element. Shearer and Kleitman conjectured in 1979 that the $𝑛$-cube has $\lfloor 𝑛/2 \rfloor + 1$ pairwise orthogonal decompositions into the minimum number of chains, and they constructed two such decompositions. Spink recently improved this by showing that the $𝑛$-cube has three pairwise orthogonal chain decompositions for $𝑛 \geq 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $𝑛$-cube for $𝑛 \geq 60$. We also construct five pairwise edge-disjoint symmetric chain decompositions of the $𝑛$-cube for $𝑛 \geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality, improving on a recent result by Gregor, Jäger, Mütze, Sawada, and Wille.
- On orthogonal symmetric chain decompositions (Karl Däubel, Sven Jäger, Torsten Mütze, and Manfred Scheucher)
EUROCOMB 2019 – Proc. European Conference on Combinatorics, Graph Theory and Applications, pp. 611–618.
@inproceedings{DaeubelJaegerMuetzeScheucher2019,
author = {D{\"a}ubel, Karl and J{\"a}ger, Sven and M{\"u}tze, Torsten and Scheucher, Manfred},
booktitle = {EUROCOMB 2019 – Proc. European Conference on Combinatorics, Graph Theory and Applications},
title = {On orthogonal symmetric chain decompositions},
year = {2019},
editor = {Nešetřil, Jaroslav and Škoviera, Martin},
month = {aug},
number = {3},
pages = {611--618},
volume = {88},
eventdate = {2019-08-26/2019-08-30},
eventtitle = {European Conference on Combinatorics, Graph Theory and Applications},
issn = {0862-9544},
journal = {Acta Mathematica Universitatis Comenianae},
url = {http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1203/701},
venue = {Bratislava, Slovakia},
}
The $𝑛$-cube is the poset obtained by ordering all subsets of $\{1, \dotsc, 𝑛\}$ by inclusion, and it can be partitioned into $\binom{𝑛}{\lfloor 𝑛/2 \rfloor}$ chains, which is the minimum possible number. Two such decompositions of the $𝑛$-cube are called orthogonal if any two chains of the decomposition share at most a single element. Shearer and Kleitman conjectured in 1979 that the $𝑛$-cube has $\lfloor 𝑛/2 \rfloor + 1$ pairwise orthogonal decompositions into the minimum possible number of chains, and they constructed two such decompositions. Spink recently improved this by showing that the $𝑛$-cube has three pairwise orthogonal chain decompositions for $𝑛 \geq 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $𝑛$-cube for $𝑛 \geq 60$. We also construct five pairwise edge-disjoint symmetric chain decompositions of the $𝑛$-cube for $𝑛 \geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality, improving on a recent result by Gregor, Jäger, Mütze, Sawada, and Wille.
- Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates (Sven Jäger)
Operations Research Letters, Elsevier BV, 46(5):505–509, 2018.
@article{Jaeger2018,
author = {J{\"a}ger, Sven},
journal = {Operations Research Letters},
title = {Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates},
year = {2018},
issn = {0167-6377},
month = {sep},
number = {5},
pages = {505--509},
volume = {46},
doi = {10.1016/j.orl.2018.07.006},
errata = {- In the first computation starting on page 5, it should be $\int_0^\infty c(s) \cdot s \,\mathrm d s$.},
publisher = {Elsevier {BV}},
}
We present a $(2 + 2 \ln 2 + 𝜀)$-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.
- Gray codes and symmetric chains (Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille)
ICALP 2018 – Proc. 45th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 66:1–66:14.
@inproceedings{GregorJaegerMuetze+2018,
author = {Gregor, Petr and J{\"a}ger, Sven and M{\"u}tze, Torsten and Sawada, Joe and Wille, Kaja},
booktitle = {ICALP 2018 – Proc. 45th International Colloquium on Automata, Languages and Programming},
title = {Gray codes and symmetric chains},
year = {2018},
address = {Dagstuhl, Germany},
editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D{\'a}niel and Sannella, Donald},
month = {jul},
number = {107},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
series = {LIPIcs},
doi = {10.4230/LIPIcs.ICALP.2018.66},
pages = {66:1--66:14},
eventdate = {2018-07-09/2018-07-13},
eventtitle = {International Colloquium on Automata, Languages and Programming},
isbn = {978-3-95977-076-7},
issn = {1868-8969},
venue = {Praha, Czech Republic},
pagetotal = {14},
}
We consider the problem of constructing a cyclic listing of all bitstrings of length $2n+1$ with Hamming weights in the interval $[n+1-\ell,n+\ell]$, where $1 \leq \ell \leq n+1$, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem ($\ell=1$). We provide a solution for the case $\ell=2$ and solve a relaxed version of the problem for general values of $\ell$, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the $n$-dimensional hypercube for any $n \geq 12$.
- Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling (Sven Jäger and Martin Skutella)
STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 43:1–43:14.
@inproceedings{JaegerSkutella2018,
author = {J{\"a}ger, Sven and Skutella, Martin},
booktitle = {STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science},
title = {Generalizing the {Kawaguchi}-{Kyan} Bound to Stochastic Parallel Machine Scheduling},
year = {2018},
address = {Dagstuhl, Germany},
editor = {Niedermeier, Rolf and Vall{\'e}e, Brigitte},
month = {feb},
number = {96},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
series = {LIPIcs},
archiveprefix = {arXiv},
doi = {10.4230/LIPIcs.STACS.2018.43},
pages = {43:1--43:14},
arxiv = {1801.01105},
eventdate = {2018-02-28/2018-03-03},
eventtitle = {International Symposium on Theoretical Aspects of Computer Science},
isbn = {978-3-95977-062-0},
issn = {1868-8969},
primaryclass = {cs.DM},
venue = {Caen, France},
}
Minimizing the sum of weighted completion times on m identical parallel machines is one of the most important and classical scheduling problems. For the stochastic variant where processing times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result, achieving, for arbitrarily many machines, performance ratio $1+\frac 1 2(1+\Delta)$, where $\Delta$ is an upper bound on the squared coefficient of variation of the processing times. We prove performance ratio $1+\frac 1 2 (\sqrt 2-1)(1+\Delta)$ for the same underlying algorithm—the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e., $\Delta=0$), our bound matches the tight performance ratio $\frac 1 2 (1+\sqrt 2)$ of this algorithm (WSPT rule), derived by Kawaguchi and Kyan in a 1986 landmark paper. We present several further improvements for WSEPT's performance ratio, one of them relying on a carefully refined analysis of WSPT yielding, for every fixed number of machines $m$, WSPT's exact performance ratio of order $\frac 1 2 (1+\sqrt 2)-O(1/m²)$.
