The Power of Proportional Fairness for Non-Clairvoyant Polytope Scheduling (Sven Jäger, Alexander Lindermayr, and Nicole Megow)
SIAM Journal on Computing, 55(2):247-279, 2026.
@article{JaegerLindermayrMegow2026,
author = {Sven Jäger and Alexander Lindermayr and Nicole Megow},
title = {The Power of Proportional Fairness for Non-Clairvoyant Polytope Scheduling},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {2},
pages = {247-279},
doi = {10.1137/25M1763974},
arxiv = {2408.14310},
archiveprefix = {arXiv},
}
The polytope scheduling problem (PSP) was introduced by Im, Kulkarni, and Munagala [J. ACM, 65 (2018), pp. 3:1–3:33] as a very general abstraction of resource allocation over time, where jobs can receive processing rates subject to arbitrary packing constraints. It captures many well-studied problems, including classical unrelated machine scheduling, multidimensional scheduling, and broadcast scheduling. An elegant and well-known algorithm for instantaneous rate allocation with good fairness and efficiency properties is the proportional fairness (PF) algorithm, which was analyzed for PSP by Im, Kulkarni, and Munagala. We drastically improve the analysis of PF 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 nonclairvoyant scheduling. Our analysis also gives the first polynomial-time improvement over the nearly 30-year-old bounds on the competitive ratio of the doubling framework, which was introduced by Hall, Shmoys, and Wein (SODA 1996) for clairvoyant online preemptive scheduling on unrelated machines. Somewhat surprisingly, we achieve this improvement by a nonclairvoyant algorithm, thereby demonstrating that nonclairvoyance 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 algebraic properties of the optimal objective value for scheduling on unrelated machines. Finally, we establish new connections between PF and matching markets and thereby provide new insights on equilibria and their computational complexity.
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{BochkarevHeeseJaeger+2026,
author = {Alexey Bochkarev and Raoul Heese and Sven Jäger and Philine Schiewe and Anita Schöbel},
title = {Quantum Computing for Discrete Optimization: A Highlight of Three Technologies},
journal = {European Journal of Operational Research},
volume = {329},
number = {3},
pages = {747--766},
year = {2026},
month = {mar},
doi = {10.1016/j.ejor.2025.07.063},
arxiv = {2409.01373},
archiveprefix = {arXiv},
primaryclass = {math.OC},
}
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.
0000-0002-7003-1430
Google Scholar