CS Paper Radar

A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size

Adam Y. Shavit

cs.DS math.OC ·submitted 2026-08-13 14:43 UTC · v3
theorycode/data

Abstract

Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for sizes s < b matches it at {1,2}. We ask how small such an instance, a witness, can be. We give a six-job witness I* on the complete graph on four machines: unit jobs form a cycle through all four, and two weight-2 jobs take the remaining edges. I* has integral optimum 3 against relaxation value 2, one job fewer than the smallest earlier witness of this class. We prove I* minimum and unique at its size, on any number of machines: no instance with at most five jobs reaches gap 3/2, and at six jobs I* is the only witness, up to relabeling machines and adding unusable machines. At seven jobs uniqueness fails: we classify all thirteen witnesses, including the Jansen-Land-Maack instance. Eight jobs give 154, nine 1,662. At least four machines are necessary. Kartak et al. (2015) classified the extremal non-round-up instances of the same relaxation in one-dimensional cutting stock for small demand; the Discussion relates them. Recognizing witnesses at relaxation value 2, shared by all ours, is coNP-complete, so no min-max characterization with polynomially checkable conditions exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating-point and exact rational arithmetic, with identical results. We accept the pipeline's negatives only after it rediscovers I*.

Comment
37 pages, 12 figures, 1 table. v3: corrects the infeasibility-verdict count behind the six-machine sweep (4,228,054, not 4,231,347), a false remark on the vertex hypothesis and two internal contradictions; the coNP consequence is stated precisely; exploratory LP bounds are labelled numerical; overstatements narrowed. Code and data: https://doi.org/10.17605/OSF.IO/SKX86

Closest papers

Nearest neighbours by meaning across the whole index.

Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6

cs.DS math.OC ·2026-09-09 ·Adam Y. Shavit
code/data similarity 0.79
Abstract · 52 pages, 11 figures. v2: new results: where the cut-term bound 3/2+1/(r+1) is attained on the three-path family (correcting v1), and strong…

Wang and Sitters' rounding scheme for graph balancing (each job allowed on at most two machines) keeps the makespan, the busiest machine's load, within 11/6 of the optimum, and a companion note shows that no smaller constant holds. One suspected cause is Step 3's freedom to match leftover jobs to slots in any valid way. We show that removing that freedom does not improve the constant. An idealized oracle that always picks the valid matching with the smallest makespan still has worst-case constant exactly 11/6 against the optimum. Both natural 7/4 bounds for it, against the relaxation's target and against the optimum, are false. Requiring Step 1 to return a vertex (corner) of the relaxation does not help when that vertex is chosen adversarially. The loss therefore does not come from Step 3's freedom alone. We also prove a reduction confining every overload above 7/4 to two shapes, give a seven-machine instance on which the natural two-phase repair fails, and prove a strict 7/4 bound on the generalized three-path family.

0.38

The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing

cs.DS math.OC ·2026-09-03 ·Adam Y. Shavit
code/data similarity 0.73
Abstract · 43 pages, 9 figures. v3: the beta < 1/2 seven-machine witness is certified in exact rational arithmetic; the strict-rule endpoint at beta = …

Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any feasible solution of the fractional relaxation. Step 3 may match remaining jobs to the rounding's slots in many ways. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, none reaching it, so 11/6 is the least constant bounding every permitted run. We then determine the worst-case guarantee, against the optimum itself, as a function of the big-job threshold beta, the fractional share at or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.

0.44

A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

cs.DS cs.DMmath.CO ·2026-09-15 ·Michel X. Goemans, Yuchong Pan
theory similarity 0.68
Abstract

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

0.23

Lower Bounds Above $\sqrt{3}$ for Online Makespan Minimization on Four Identical Machines

cs.DS math.OC ·2026-11-07 ·Maximilian Janke
theory similarity 0.67
Abstract

For deterministic online makespan minimization, $m = 4$ identical machines is the smallest case whose optimal competitive ratio is open: it is known only to lie between $\sqrt{3} \approx 1.73205$ and $26/15 \approx 1.73333$. We prove a lower bound of $14383/8304 \approx 1.73206$ using a single branching layer, and refine the construction with a second, mirrored branching layer to obtain $14350/8283 \approx 1.73246$, closing about a third of the gap. Our constructions are the first branching adversaries for $m = 4$ machines, and the first explicit lower bounds for online makespan minimization in which the adversary presents jobs in non-monotone order of size.

0.49

Integrality gap preserving reductions

cs.DM cs.DS ·2026-09-17 ·Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
theory similarity 0.65
Abstract · 30 pages, 2 figures

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

0.42

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization

cs.DS ·2026-10-26 ·Weitian Tong, Yao Xu
similarity 0.65
Abstract · 34 pages, 8 figures

We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.

0.15

Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound

cs.GT ·2026-11-03 ·Wenqian Wang, Chenyang Xu, Yuhao Zhang
theory similarity 0.64
Abstract · 42 pages, 2 figures

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, asserts that no deterministic truthful mechanism for makespan minimization on $m$ unrelated machines can achieve an approximation ratio better than $m$. Christodoulou, Koutsoupias, and Kovács resolved it in 2023, but the optimal approximation ratio achievable by randomized truthful mechanisms remained open. Recently, Anastasiadis, Christodoulou, Koutsoupias, Kovács, and Schecker extended techniques from the deterministic proof to establish a $(3/2-\sqrt{2})(m-1)$ lower bound for universally truthful mechanisms with discrete support and gave a universally truthful mechanism with approximation ratio $m/2+o(m)$. For the broader class of truthful-in-expectation (TIE) mechanisms, however, the gap remained large: the best known upper bound was $(m+5)/2$, while the lower bound was only $2-1/m$. We prove a lower bound of $(m+1)/2$, determining the optimal TIE approximation ratio up to an additive constant as $m/2+Θ(1)$. Our result also improves the leading constant in the lower bound for universally truthful mechanisms from $3/2-\sqrt{2} \approx 0.0858$ to $1/2$. Together with their $m/2+o(m)$ upper bound, our result determines the optimal approximation ratio for universally truthful mechanisms up to lower-order terms.

0.20

When is greedy exact for weighted minimum 3-cut?

cs.DS ·2026-10-26 ·Armando Rodado Amaris
theorycode/data similarity 0.62
Abstract · 16 pages. Lean 4 proofs and Python reproduction scripts are provided as ancillary files and at https://github.com/armandorodado/minimum-3cut…

The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.

0.44