PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Adam Y. Shavit

arXiv:2609.03890v1cs.DSmath.OC

TL;DR

The paper asks what performance the non-deterministic Wang–Sitters rounding scheme can actually produce, since feasible relaxation solutions and slot matchings are not uniquely chosen. It characterizes the resulting worst-case guarantees across every threshold, showing that 11/6 is approached but never attained and that the threshold-dependent guarantee changes sharply at one half.

  • Problem

    The Wang–Sitters scheme permits multiple feasible relaxation solutions and valid slot matchings, so its makespan on a fixed instance is a set of possible values rather than a single output.

  • Method

    The paper analyzes all permitted choices in Steps 1–3, constructs matching lower-bound families, and proves converse bounds for the resulting executions across the threshold range.

  • Results

    11/6 is the supremum and is never attained; the guarantee is exactly max{3/2 + β/2, 5/2 − β} for 1/2 < β < 1 and exactly 3/2 + (1 − β)⌊1/β⌋ below one half.

  • Takeaways & Limitations

    The worst-case ratio is characterized throughout β ∈ (0,1), with the threshold behavior changing at one half rather than degrading smoothly.

  • Takeaways & Limitations

    Some supporting checks are computational rather than rational certificates, and one family requires a parameterized construction because perturbing shares changes the associated load budget.

Abstract

from arXiv · show

Wang and Sitters' 11/6-approximation for graph balancing is not one algorithm but a set of permitted executions: Step 1 may return any feasible solution of the relaxation and Step 3 any of the many ways to match the remaining jobs into the slots the rounding opens. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, and none reaching it, so 11/6 is the least constant that bounds every permitted run, and no run attains it. We then determine the worst-case guarantee as a function of the big-job threshold beta, measured against the optimum itself. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We then extend the same eligibility rule to 0 < beta <= 1/2 -- outside the range they state, and where a big job's two shares can both reach the threshold, so Step 2 acquires a third choice -- and determine the guarantee there as well: 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 rather than degrading smoothly. A companion note asks what does not fix the constant.

1 Introduction

The Wang–Sitters scheme permits multiple executions because its relaxation solution and slot matching are not uniquely determined. This note characterizes the resulting worst-case ratios across thresholds, showing that 11/6 is a nonattained supremum and that 2/3 is uniquely optimal.

  • The approximation ratio: The scheme is set-valued because Step 1 may return different feasible relaxation solutions and Step 3 may choose among many valid slot matchings.Thus its makespan on a fixed instance is a set of possible values rather than a single output.
  • The approximation ratio: 11/6 is the tight approximation supremum against OPT, approached by valid executions but never attained.Theorem 2 supplies instances with makespan 11/6 − δ, while Proposition 5 proves every valid run is strictly below 11/6.
  • The threshold: For 1/2 < β < 1, the exact guarantee is max{3/2 + β/2, 5/2 − β}.The lower and matching upper bounds establish this threshold-dependent guarantee.
  • The threshold: Across β ∈ (0,1), the worst-case ratio is known and attained at no threshold, with 2/3 the unique optimal threshold.The two threshold branches are combined into a single exact function measured against the optimum.
  • What does not fix the constant: Optimizing Step 3 or restricting Step 1 to a relaxation vertex does not reduce the worst-case constant below 11/6.The companion note establishes these negative results; this note cites rather than reproves them.

2 Preliminaries

The scheme runs at the least feasible relaxation target, but its feasible solution and slot matching are generally non-unique. Its rounding depends on a half-open slot convention that is essential for the strict 11/6 ceiling.

  • The target: The least feasible target T is attained and is no larger than OPT, because an integral optimum is also feasible for the relaxation at OPT.The relaxation’s changing big-job set requires care at breakpoints, but compactness establishes attainment.
  • The execution space: The scheme evaluates executions consisting of a feasible relaxation solution and a valid slot matching, rather than a uniquely specified schedule.At or below β = 1/2, Step 2 also acquires a choice, so the execution is represented by a triple rather than a pair.
  • The three steps: At β = 2/3, Step 2 assigns every big job whose fractional share reaches β, then Step 3 matches remaining jobs to adjacent slots.Because β > 1/2, the relaxation permits at most one such big job per machine.
  • Slot rounding: The slot structure orders fractional jobs by nonincreasing size, cuts fractional mass into unit slots, and uses half-open adjacency.A fraction ending exactly at a slot boundary is not adjacent to the following slot.
  • Slot rounding: The half-open convention is necessary: under the closed reading, a three-job instance has a valid matching with makespan 99/50 = 1.98, exceeding 11/6.The closed reading adds an edge at the boundary, allowing both big jobs onto one machine; the half-open reading has six valid matchings and worst makespan 199/200.

3 The approximation ratio is tight at 11/6

The scheme’s 11/6 guarantee is tight as a supremum but unattained: explicit executions approach it while every valid execution remains strictly below it. The witness relies on freedom in both relaxation selection and slot matching.

  • The lower bound: For every δ ∈ (0, 1/6), a three-machine, three-job instance with OPT = 1 admits an execution whose makespan approaches 11/6 from below.The construction is feasible at T = 1 and infeasible below T = 1.
  • The lower bound: The witness uses a valid matching that places all three jobs on one machine, producing makespan 11/6 − δ.The matching respects slot adjacency and uses each slot at most once.
  • The execution latitude: The bad relaxation point is non-vertex, and the construction therefore exercises Step 1’s freedom as well as Step 3’s matching freedom.A feasible segment contains the point, while the bad region is an open sliver of width 2δ.
  • The execution latitude: The companion construction shows that restricting Step 1 to basic feasible solutions does not remove the 11/6 phenomenon, although it avoids this particular witness.A separate vertex-based family has every valid matching near 11/6.
  • The upper bound: Every valid execution has makespan strictly below 11/6, so the worst-case ratio is a supremum that no run attains.The proof partitions machines according to Step 2 and the slot-1 occupant, with strictness supplied by the positive last slot.
  • The upper bound: The ratio statement requires running at the least feasible target, because the bound is on ALG/T while the approximation ratio is ALG/OPT.At that target, T ≤ OPT; an instance run above its least feasible target can invalidate the conclusion.

4 A weaker family, tight only against the relaxation

The six-job family makes the Wang–Sitters rounding tight against the relaxation target, but not against the true optimum. Its valid matching can approach 11/6 relative to T, while the family’s optimum is approximately 4/3 times T.

  • Construction: The family’s relaxation solution is essentially forced, making it a clean illustration of the slot mechanism.Figure 5 compares arbitrary matching with the best-matching variant.
  • Slot matching: Three slots on one machine absorb sizes T, T/2, and T/3, realizing the three terms in the Wang–Sitters analysis simultaneously.The matching places q, h, and r into slots 1, 2, and 3.
  • Theorem 10: 11/6 T − O(δ) is achieved by a valid matching on a six-job, four-machine instance feasible at T = 1 + 2δ.The feasible region is confined to an O(δ)-width box.
  • Approximation ratio: OPT = 4/3 + 5δ/2, so the realized ratio is 11/6 divided by 4/3 + 5δ/2 and tends to 11/8, not 11/6.The forced singleton construction makes the relaxation feasible at T and infeasible below T.
  • Measurements: At δ = 10^-3, the arbitrary matching gives ALG/OPT = 1.3724267, whereas the best-matching oracle gives ratio exactly 1.0000.The same instance has ALG/T = 1.8296740 and OPT/T = 1.33317 at that δ.
  • Threshold dependence: The family is not β-independent: Step 2 assigns its big job when β ≤ 2/3 − δ, collapsing the ratio, and it binds only above that threshold.Neither this family nor Theorem 2 shows that no threshold choice helps; later results settle that question.

5 Relation to Schwartz and Yeheskel

The section distinguishes relaxation-relative phenomena from guarantees against the optimum and relates them to Schwartz and Yeheskel’s results. It establishes the exact threshold-dependent guarantee above one half, including its unique minimizer, while extending the analysis below one half.

  • Scope: No per-vertex strengthening between the original relaxation and the configuration program is shown here to improve the rounding constant.The configuration program already implies these cuts, while whether an intermediate strengthening helps remains open.
  • Relation to prior work: The cited Figure-4 instances reach about 1.37 against OPT, not near 11/6; Theorem 2 supplies the plain graph-balancing witness.Their other results concern the larger model GBu(0.5) or are bicriteria and LP_k-relative.
  • Optimal threshold: 11/6 is attained as the exact threshold guarantee at β = 2/3 only in the supremum sense: every execution is strictly below 11/6, while Theorem 2 approaches it.At β = 2/3, T_LP = OPT = 1 on the approaching family.
  • Lower-bound families: The lower bounds 3/2 + β/2 and 5/2 − β are approached by separate families as perturbations vanish, rather than realized by a single instance.The threshold test’s strict and non-strict forms agree on these constructions because the relevant shares lie strictly on opposite sides of β.
  • Guarantee above one half: The guarantee against OPT is exactly g(β) = max{3/2 + β/2, 5/2 − β} for every 1/2 < β < 1, and no execution attains it.Every execution remains strictly below g(β)T, while matching families approach both branches.
  • Extension below one half: For 0 < β ≤ 1/2, the nested collector family yields makespan approaching 3/2 + (1 − β)m with T_LP = OPT = T.The execution is legal for β ≤ α, and under the strict reading whenever β < α.

6 Below one half, the guarantee is unbounded as β →0

For β ≤ 1/2, Step 2 gains an additional assignment choice because multiple big-job shares can meet the threshold. The resulting optimum-relative guarantee is exact at every threshold, grows without bound as β decreases, and jumps at reciprocal thresholds.

  • Why the analysis changes: At β ≤ 1/2, Step 2 becomes a choice because two shares can meet the machine budget and both shares of one job can reach β.Above one half, neither situation can occur.
  • Why the analysis changes: ⌊1/β⌋ big jobs can fit under one machine’s big-job budget, which determines the lower-half guarantee’s growth.The relevant shares are each at least β and sum to at most 1.
  • Threshold behavior: The guarantee is unbounded as β → 0 and is piecewise affine between reciprocal thresholds.Its slope steepens by one unit at each reciprocal threshold.
  • Threshold behavior: At β = 1/k, the guarantee equals k + 1/2 as a supremum, while the curve jumps because the admissible-job count changes.At β = 1/2, the value is 5/2.
  • Exact guarantee: 3/2 + (1 − β)⌊1/β⌋ is the exact guarantee against OPT for 0 < β ≤ 1/2, approached but never attained.The matching construction has TLP = OPT = T and approaches the bound.
  • Global conclusion: Across all thresholds, β = 2/3 is the unique minimizer, the supremum is never attained, and the guarantee jumps at one half.The optimum-relative branches agree on the same unique minimizer.

7 What this note establishes

The note establishes the exact behavior of the Wang–Sitters scheme across all thresholds: 11/6 is a never-attained supremum, and the optimum-relative guarantee is determined throughout (0,1). The unique best threshold is 2/3, while the guarantee jumps at one half and becomes unbounded as the threshold decreases.

  • 11/6 supremum: 11/6 is the least universal bound: permitted executions approach it arbitrarily closely, but no instance or execution attains it.Theorem 2 supplies executions with ratio 11/6 − δ, while Proposition 5 keeps every machine strictly below 11/6 T.
  • Threshold guarantee: For 1/2 < β < 1, the exact guarantee is g(β) = max{3/2 + β/2, 5/2 − β}.The lower and upper bounds are proved across the full interval, not only at sampled thresholds.
  • Threshold guarantee: At or below one half, every big job is seized in Step 2, allowing a machine to receive ⌊1/β⌋ such jobs.The resulting lower-bound family has TLP = OPT, so the ratio is measured directly against the optimum.
  • Threshold guarantee: For 0 < β ≤ 1/2, the exact optimum-relative guarantee is 3/2 + (1 − β)⌊1/β⌋, approached but never attained.Theorem 22 gives the ceiling, and Theorem 25’s nested family reaches it in the limit.
  • Threshold guarantee: β = 2/3 is the unique minimizer over (0,1), and the guarantee is unbounded as β falls.The two threshold regions do not join smoothly: at β = 1/2 the guarantee is 5/2 while it tends to 2 from above.
  • Scope: Changing the threshold cannot improve the approximation ratio for graph balancing, which remains 1.75.The note leaves open whether a different relaxation or a non–Shmoys–Tardos rounding rule could move the constant.

A Restatement checks

The restatement checks compare each theorem’s quantifiers with the proof and distinguish universal claims from exhibited examples. For the supremum construction, the proof explicitly supplies one legal execution per δ rather than claiming all executions are bad.

  • A Restatement checks: The checks ask whether each result’s quantifiers match its proof, including which objects are universal and which are merely exhibited.They are intended for verification rather than for following the paper’s main argument.
  • A Restatement checks: Lemma 1 is proved for every eligible machine and valid matching using only sort order, slot lengths, and the one-job-per-slot cap.The proof requires no hypothesis on x beyond relaxation feasibility.
  • A Restatement checks: The 11/6 − δ claim exhibits an instance, feasible relaxation solution, legal Step-2 assignment, and valid matching for each δ; it does not claim every run is bad.The supremum follows because δ ranges over an interval with infimum 0.

Proposition 5

Proposition 5 proves a strict per-machine bound below 11/6 T for every instance, feasible relaxation solution, and valid slot matching. Its case analysis depends on the half-open slot convention and tracks the relevant Step-2 job size.

  • Proposition 5: The proposition quantifies over all instances, feasible relaxation solutions, valid matchings, and machines, proving a strict inequality in three exhaustive cases.Strictness comes from different conditions in cases (S), (N0), and (N1).
  • Proposition 5: The case analysis sharpens the earlier flat 5/2 − β bound by tracking the Step-2 job’s own size, with a parametrized 2 − x_q/2 bound in case (N1).Cases (N0) and (S) correspond, up to notation, to two cases in prior work.
  • Proposition 5: The bound applies to every valid matching because b_max, p_max, and σ depend only on the instance, x, and Step 2, not on the matching.The two branches are attained only in the limit and only at their respective corners.
  • Proposition 5: The proposition yields a 7/4 certificate when every Step-2 job is at most 3/4 and every job is at most 7/8.This is a certificate for a particular run because σ depends on x and Step 2, not a bound for an instance class alone.

Theorem 10

Theorem 10 establishes a family whose matching makespan approaches 11/6 T and whose approximation ratio against the true optimum tends to 11/8. It is therefore tight only relative to the relaxation target, not the optimum.

  • Theorem 10: 11/6 T − O(δ) is the family’s matching makespan, while its exact optimum gives an ALG/OPT limit of 11/8.The theorem establishes relaxation feasibility at T, the relevant matching, the exact OPT, and the resulting limit.
  • Theorem 10: Theorem 10 does not claim tightness of the approximation ratio; that conclusion belongs to Theorem 2.

Proposition 15

Proposition 15 establishes a threshold-relative guarantee against the relaxation target T over β ∈ (1/2,1), with strict separation from 11/6 except at β = 2/3.

  • Threshold-relative guarantee: The construction is uniform over β ∈ (1/2,1), because its required conditions reduce to comparisons between affine functions of β.Both bad-instance families are parameterized by β and cover an interval rather than only a single threshold.
  • Threshold-relative guarantee: For every β ≠ 2/3, the threshold-relative guarantee satisfies RT(β) ≥ g(β) > 11/6 = RT(2/3).The proposition’s lower bound uses a floor, while the matching upper bound is established separately in Proposition 16.

Propositions 16 and Corollary 17

Propositions 16 and Corollary 17 complete the threshold-relative analysis on β ∈ (1/2,1): the strict upper bound is attained as a supremum but never by an execution.

  • Proof conditions: The proof’s cases inherit the half-open slot convention and re-derive that a machine holding a Step-2 job has no unassigned big fraction.These hypotheses ensure the case analysis is exhaustive at general β in the stated range.
  • Propositions 16 and Corollary 17: The corollary’s equality is a supremum, not a maximum: every execution lies strictly below the ceiling, while perturbation families approach it.Therefore no permitted execution attains the threshold-relative bound.
  • Scope boundary: The result does not extend Proposition 5’s case split to β ≤ 1/2, where that split is not exhaustive and Section 6 is required.The stated threshold interval is therefore a genuine scope boundary of this argument.

Lemma 21 and Theorem 22

Lemma 21 and Theorem 22 extend the analysis below β = 1/2, using the enlarged Step-2 execution space and a bound stated against ALG/T that also implies an optimum-relative bound.

  • Lemma 21 and Theorem 22: At β ≤ 1/2, a big job’s two shares can both reach the threshold, enlarging the legal Step-2 assignment choices.The theorem therefore quantifies over all legal Step-2 assignments and valid matchings.
  • Lemma 21 and Theorem 22: The lemma relies on each job being supported on at most two machines and its fractional shares summing to one.Instances outside that graph-balancing restriction are outside the lemma’s scope.
  • Lemma 21 and Theorem 22: The theorem applies Lemma 1(ii) with the total Step-2 size replacing a single Step-2 job’s size, yielding a bound on ALG/T.Because TLP ≤ OPT, this guarantee is at least as strong when measured against the optimum.
  • Lemma 21 and Theorem 22: The theorem is existential: for each β it gives one instance, feasible solution, legal Step-2 assignment, and valid matching, rather than making every execution bad.Measurement 36 verifies the maximum over all such choices on those instances.

Code and data

The paper deposits the code, artifacts, logs, driver, and pinned dependencies needed to reproduce its computational results, with one documented figure-script exception.

  • Code and data: The Open Science Framework deposit contains claim-supporting scripts, generated artifacts and logs, a regeneration driver, and pinned dependency versions.A README maps each claim to the corresponding command.
  • Code and data: Every numerical measurement reported in the note is reproducible from the deposited code and artifacts.The deposited package is the replication set rather than the project’s working directory.
  • Code and data: The Figure 7 drawing script is not deposited because Figure 7 plots closed forms proved in the text rather than measured results.Exploratory proof attempts and the internal revision diary are also excluded from the public replication set.

Authorship and computational process

The author conceived and directed the work, while AI systems assisted with writing, review, simulations, and discovery of the three-job family. Computational results are supported by deposited materials, but the author did not personally inspect every generated code line or independently repeat every computation.

  • The author conceived and directed the work and takes responsibility for the paper’s claims.
  • AI systems assisted with writing, adversarial review, simulations, and discovery of the three-job family.The family was subsequently checked using deposited verification and the proof in the paper.
  • The computational results are supported by deposited code, artifacts, exact checks, cross-checks, and positive controls.
  • The author did not personally inspect every generated code line or independently repeat every computation.

Author’s note

The author presents the work as community-supported research, emphasizing public computational records and replication materials that map reported results to code and stored artifacts or logs.

  • The work is offered in the spirit of community-supported research, where computing is contributed, records are public, and value comes from what others can build on it.
  • The public replication package maps every reported computational result, including searches that found nothing, to producing code and stored artifacts or logs when available.
Loading 2609.03890v1…