PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Adam Y. Shavit

arXiv:2609.10004v1cs.DSmath.OC

TL;DR

The paper asks whether arbitrary valid matching selection is responsible for the Wang–Sitters scheme’s 11/6 loss. It analyzes minimum-makespan matching and vertex-restricted solutions, finding that the worst-case constant persists and the natural 7/4 guarantees fail.

  • Problem

    The companion note’s 11/6 bound raises whether the loss comes from allowing any valid slot matching in Step 3.

    Source: §1 · p. 1

  • Method

    The paper constructs counterexamples for minimum-makespan matching and a separate family whose relaxation solution is already a vertex.

    Source: §1 · p. 1, §5 · pp. 23, 25

  • Results

    The oracle’s worst-case ratio to OPT is exactly 11/6, and the threshold-relative and OPT-relative 7/4 guarantees are both false.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The loss is not confined to nonvertex solutions: the later construction starts at a vertex because walking to one destroys the edge behind the bound.

    Source: §5 · p. 25

    The threshold-relative counterexample is not a vertex, so it does not alone settle the vertex-restricted variant.

    Source: §3 · p. 9

Abstract

from arXiv · show

The 11/6 worst-case constant of the Wang-Sitters rounding scheme, which a companion note establishes, can naturally be attributed to the freedom in Step 3, where an arbitrary valid slot matching is permitted. We show that eliminating that freedom does not improve the constant. A minimum-makespan completion oracle still has worst-case constant exactly 11/6 against the optimum; both natural 7/4 statements about it are false; and restricting Step 1 to vertices of the relaxation does not help. The loss therefore cannot be attributed solely to the freedom in Step 3. We also record what structure survives: a reduction confining every overload to two shapes, a seven-machine instance defeating the natural two-phase repair, and a strict 7/4 bound on the generalized three-path family.

1 Introduction

The companion note [1] establishes the Wang–Sitters scheme’s 11/6 worst-case constant, prompting the question of whether arbitrary matching selection causes the loss. This paper shows that a minimum-makespan matching and vertex-restricted relaxation solutions do not improve that constant.

1 Introduction

  • 11/6 remains the exact worst-case constant against the threshold even when Step 3 chooses a minimum-makespan valid matching.The threshold-relative 7/4 statement is also false: at the least feasible threshold, every valid matching reaches 44/25 > 7/4 on a 19-machine instance.Source: §1 · pp. 1–2
  • The threshold and optimum versions of the 7/4 conjecture are distinct claims, refuted by different instances.The threshold-relative counterexample is nonvertex, which is why the vertex-restricted case is settled separately.Source: §1 · p. 2
  • 11/6 is also the oracle’s exact worst-case ratio against OPT; at g = 4, every valid matching reaches 85/48 > 7/4.The instance gives each unit job its own partner machine, preserving forced loads while reducing OPT to 1.Source: §1 · p. 2
  • Restricting Step 1 to relaxation vertices still leaves the 11/6 supremum against both the threshold and OPT, for every matching-selection rule.The vertex family has T = OPT = 1; the supremum is not attained.Source: §1 · p. 2
  • The paper also confines overloads above 7/4 to two shapes, defeats a natural two-phase repair, and proves a strict 7/4 bound for the generalized three-path family.The three-path family is identified as extremal for the relaxation.Source: §1 · p. 2
  • The paper distinguishes proved body claims from measurements, which are labeled and documented separately in Appendix A.Its candidate 7/4 guarantees were disproved by separate instances, not found by searching.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the relaxation, the rounding steps, and the execution choices that later results analyze. They also state without proof the companion note’s bounds and families used in the arguments.

2 Preliminaries

  • The relaxation is run at target T; its least feasible value TLP is attained and satisfies TLP ≤ OPT, though the two values may differ.It assigns job fractions to at most two eligible machines, fully places each job, limits machine load to the target, and caps each machine at one big job’s worth of fraction.Source: §2 · p. 3
  • The relaxation has integrality gap exactly 7/4, while the configuration linear program is strictly stronger; the paper makes no rounding claim about that stronger relaxation.The upper bound cited is the algorithm of [5], and the lower bound is its three-path family; unless P = NP, graph balancing has no polynomial-time algorithm with ratio strictly below 3/2.Source: §2 · p. 3
  • Wang and Sitters’ three-step scheme takes a feasible relaxation solution, schedules a big job when its fraction reaches β = 2/3, then matches remaining jobs to slots.A scheduled big job is removed from both machines’ fractional assignments; the relaxation’s third constraint and β > 1/2 prevent a machine receiving two such jobs.Source: §2 · pp. 3–4
  • The slot construction orders fractional jobs by nonincreasing size, cuts fractional mass into unit slots, and connects each job to slots its fraction touches under a half-open convention.A valid matching assigns each remaining job to one adjacent slot, with at most one job per slot; Hall’s theorem ensures one exists.Source: §2 · p. 4
  • The analysis separates the scheme’s execution space from an implementation: the former allows any feasible x and valid matching, while the oracle uses a makespan-minimizing matching.An implementation realizes one solver- and routine-determined execution; the theorems concern the scheme or oracle, not that single execution.Source: §2 · p. 4
  • The companion note’s 11/6 ceiling [1] applies when the relaxation is feasible at T and a valid Step 3 matching uses β=2/3; every machine’s load is strictly less than 11.Source: §2 · p. 5

3 The threshold-relative constant is exactly 11

This section establishes that the threshold-relative worst-case constant for minimum-makespan valid slot matching is exactly 11/6. It also shows that the two natural 7/4 guarantees are false, with a family on which every matching is rigid and the best-matching oracle cannot improve the outcome.

3 The threshold-relative constant is exactly 11

  • Both natural 7/4 guarantees are false, but for different instances: the threshold-relative form is refuted by Theorem 4 and the optimum-relative form by Theorem 9.The threshold-relative form would imply the optimum-relative form because TLP ≤ OPT, but the converse need not hold.Source: §3 · p. 6
  • The relaxation’s 7/4 integrality gap does not guarantee that slot-matching rounding reaches 7/4 relative to the threshold.Theorem 4 has OPT/TLP = 3/2 while every valid slot matching has makespan 44/25; the integrality gap bounds OPT/TLP, not a particular rounding’s output relative to T.Source: §3 · p. 6
  • Theorem 9 rules out a 7/4 selection rule when Step 1 may return any feasible solution, but does not rule out restricting Step 1 to a vertex of the relaxation.The vertex-restricted question is left open in this discussion and is settled separately by Theorem 12, not by perturbing Theorem 4’s instance.Source: §3 · pp. 6, 7, 9
  • 44/25 is the makespan forced on every valid matching by a 19-machine instance at its least feasible threshold T = 1, despite OPT = 3/2.This refutes the threshold-relative 7/4 guarantee; on the instance, ALG/OPT = 88/75.Source: §3 · p. 7
  • 11/6 is the exact threshold-relative constant for best-matching slot rounding, although every instance finishes strictly below 11/6 times its threshold.The upper bound is imported from the companion note [1], while the new lower-bound family shows the constant is a supremum, not an attained value.Source: §3 · p. 10
  • The lower-bound theorem needs both choices, and naming only the A jobs names just one of them.Source: §3 · p. 13
  • 11/6 is the exact threshold-relative constant: forced loads 11/6 - 1/(4g) approach it, and [1]’s ceiling makes 11/6 admissible.The construction forces an Ak onto its blocker, where it joins a unit job and Dk; the load is 11/6 - 1/(4g).Source: §3 · pp. 12–13
  • For every g ≥ 1, every valid slot matching has makespan Fg = 11/6 - 1/(4g), while OPT = Og = 4/3 - 1/(4g); the family admits no better matching or schedule.Source: §3 · pp. 13, 15
  • Figure 3 separates 1.749 as an integrality-gap bound from the 11/6 threshold-relative constant, and distinguishes Theorem 4’s 44/25-to-threshold from 88/75-to-OPT.The figure also identifies the plain algorithm’s and best-matching oracle’s 11/6 worst ratios to OPT as distinct from threshold-relative tightness.Source: §3 · p. 13, Figure 3 · p. 14
  • For g = 2, jointly raising the share by 10−2 and lowering the size by 5 · 10−3 reduces the forced load, each perturbation lowering it by exactly its own size.Source: §3 · p. 15

4 The oracle is not a 7 4-approximation

Giving every unit job its own partner lowers the optimum to 1 without changing the forced load, so the minimum-makespan matching oracle can exceed 7/4 against OPT. Its worst-case ratio is exactly 11/6 as a supremum, and the supremum is not attained.

4 The oracle is not a 7 4-approximation

  • At g = 4, the oracle’s ratio is 85/48 > 7/4; the family reaches exactly 7/4 at g = 3, with OPT = 1 and every valid matching forced to at least 11/6 − 1/(4g).The bound is exact for some valid matching; Figure 5 highlights g = 4 as the first member above 7/4.Source: §4 · pp. 16, 19, Figure 5 · p. 18
  • Theorem 9 changes only the partners: feasibility and the forced load are inherited, while the modified family’s OPT falls to 1.The lower-bound count uses crammer and sink slots; partners do not enter it.Source: §4 · pp. 16, 19
  • Theorem 6’s ratio is largest at g = 1 and falls toward 11/8, whereas the modified family’s ratio rises and first exceeds 7/4 at g = 4.The two families share the forced-load construction, but changing partner count changes the optimum.Source: §4 · pp. 16–17, Figure 4 · p. 17
  • The oracle’s worst-case ratio to OPT is exactly 11/6 as a nonattained supremum, with the family’s ratios approaching 11/6.The universal upper bound applies to every feasible Step 1 solution and valid matching.Source: §4 · pp. 19–20
  • On this family, a solver’s Step 1 outputs finish at OPT for g = 1, . . . , 4, but the theorem covers every feasible Step 1 output.The adversarial feasible point must be supplied explicitly; the result concerns the scheme as specified, not a particular solver’s behavior.Source: §4 · p. 20

5 A vertex in Step 1 buys nothing

This section shows that restricting Step 1 to relaxation vertices does not eliminate the 11/6 obstruction: the vertex-restricted ALG/OPT supremum is unchanged for arbitrary and minimum-makespan Step 3.

5 A vertex in Step 1 buys nothing

  • For every g ≥ 2, a vertex solution with T = OPT = 1 on 10g + 3 machines forces every valid Step-3 matching to attain makespan 11/6 − 1/(4g), leaving the vertex-restricted ALG/OPT supremum at 11/6.At g = 4, the forced makespan is 85/48, greater than 7/4.Source: §5 · p. 22
  • Vertexhood is proved uniformly by showing the tight constraints have full rank: pad constraints split off, and the remaining rows reduce to the incidence matrix of a tree.The rank is 22g + 4, equal to the number of variables, for every g ≥ 2.Source: §5 · p. 24
  • Padding jobs pin the small ε share from the outset, preserving the slot-graph edge that purification of the earlier family destroys.The theorem’s bound is over every valid matching, so it does not depend on an adverse Step-3 choice.Source: §5 · pp. 21, 25, 26
  • Purifying the earlier family removes its ε-supported edge and lowers its forced load from 85/48 to 61/48 at g = 4, whereas padding constructs a different vertex that retains the edge.The reported purification paths provide evidence for why a vertex restriction looked promising, but do not negate the padded family’s theorem.Source: §5 · pp. 25–26
  • The bound uses big jobs of size > T/2 and Step 2’s non-strict ≥β test; changing either published boundary reading makes the construction infeasible or lowers its forced load below 7/4.With size ≥ T/2 the crammer’s big-job row exceeds 1; with a strict Step-2 test the forced load falls to 5/3.Source: §5 · pp. 25–26
  • For every g ≥ 2, sharing the dumps yields a vertex instance on 5g + 2 machines and 12g + 2 jobs with T = OPT = 1, where every valid slot matching has makespan 11/6.The compressed construction halves the leading machine-count constant; checks at g = 2, 3, 4 confirmed feasibility, full rank, the minimum over valid matchings, and the stated schedule.Source: §5 · pp. 26–27
  • The vertex-restricted ALG/OPT supremum remains 11/6 whether Step 3 returns an arbitrary valid matching or a minimum-makespan matching, and neither supremum is attained.The vertex construction forces every valid matching to have makespan 11/6 when T = OPT = 1.Source: §5 · pp. 26–27

6 OPT. So 11

A minimum-makespan oracle and vertex-restricted Step 1 leave the worst-case ratio at 11/6; none of the four suprema is attained.

6 OPT. So 11

  • 11/6−1/(4g) is a lower bound for every valid matching on the vertex family at T = OPT = 1, approaching 11/6 as g grows.Because the bound holds for every matching, it also holds for any matching-selection rule.Source: §6 · p. 27
  • Any deterministic or randomized Step-3 selection rule leaves the constant at 11/6 against both the threshold and the optimum, with either Step-1 domain.For randomized rules, every matching in the support satisfies the lower bound with probability one.Source: §6 · p. 27
  • Across feasible and vertex cases, each with arbitrary and minimum-makespan variants, the four ratios all have supremum 11/6, and none of the four suprema is attained.Source: §6 · p. 28
  • At g = 4, the vertex family’s minimum over valid matchings exceeds 7/4 and approaches 11/6 without reaching the strict ceiling.The theorem proves the closed-form curve for every g ≥ 2; deposited certificates record minima at eight parameters.Source: §6 · p. 28
  • One extra sink slot cuts the lower bound by exactly 1/2; removing partner padding costs vertexhood, and dropping two pads also destroys it.Source: §6 · p. 29
  • 36571/20000 is a certified lower bound on the vertex-restricted worst-case ratio, while Theorem 12 closes the remaining gap to 11/6.The witness has thirteen machines and twenty-three jobs, with a worst valid matching makespan of 36571/10000.Source: §6 · pp. 29–30
  • The 13-machine witness needs no adversarial Step-3 choice: the implementation’s augmenting-path rule returns its worst matching.Its size-2 job has shares 3363/10000 and 6637/10000, so Step 2 leaves it unplaced at β = 2/3.Source: §6 · p. 30

6 Choosing the matching, and the cost of choosing well

The section defines a minimum-makespan completion oracle and examines its guarantees and computational cost. It also establishes structural facts about slot matchings and distinguishes results for particular feasible solutions from claims over all choices of Step 1.

6 Choosing the matching, and the cost of choosing well

  • The oracle keeps Steps 1 and 2 unchanged and chooses a makespan-minimizing valid matching in Step 3; its completion problem for a supplied fractional solution is NP-complete.The hardness result concerns a given x, not the instance-level variant where Step 1 chooses x.Source: §6 · pp. 30, 32
  • On the exhibited solutions of the two families from [1], minimum-makespan completion equals OPT, but that result does not hold for every feasible solution on the instance.The section gives an endpoint solution on the 11/6 family where the oracle’s makespan is 4/3 − δ against OPT = 1.Source: §6 · pp. 30–31
  • Every valid matching is covered by the 11/6 ceiling, so a makespan-minimizing valid matching is covered as well.The prior 11/6 family also has a best matching of makespan 1 = OPT, unlike its worst matching at 11/6 − δ.Source: §6 · pp. 30–31
  • In a slot graph, every job–slot edge belongs to some valid matching; a job can avoid a slot exactly when it has at least two adjacent slots.Thus a job of slot-degree at least two is not individually forced to any particular slot, and overload obstructions involving such jobs must be collective.Source: §6 · pp. 31–32
  • For a supplied feasible solution, deciding whether a valid matching has makespan at most T is NP-complete, via a reduction from Partition.The theorem is weakly NP-complete and does not rule out pseudo-polynomial or fixed-parameter algorithms.Source: §6 · pp. 32–33
  • A tested greedy completion rule reaches ratios of 2.027 and 2.2382 on reported instances, but this solver-dependent measurement is not a claim about every polynomial-time rule.The section explicitly distinguishes this rule from completions that ignore the slot structure, including exact residual assignment.Source: §6 · p. 33

7 Above 7 4, a machine has one of two shapes

The section reduces machines exceeding 7/4 to two overload shapes and studies a proposed two-phase way to avoid them. A seven-machine example defeats the first phase, while the reduction itself does not show the shapes can be routed away.

7 Above 7 4, a machine has one of two shapes

  • At T = 1, conditions (R1) and (R2′) together guarantee makespan at most 7/4; (R2′) constrains the slot-1 job where a Step-2 job exceeds 3/4.Avoiding both overload shapes is sufficient for the threshold-relative bound, but not necessary for its optimum-relative form.Source: §7 · pp. 33–34
  • Any machine above 7/4 has one of two shapes: no Step-2 job and a matched big job with share below 1/2, or a Step-2 job larger than 3/4.The second shape can exceed 7/4 by at most 1/12.Source: §7 · p. 34
  • The reduction makes both hypotheses structural, but does not show a matching can satisfy them; the two-phase strategy therefore remains unsupported.Theorem 4 and Theorem 6 establish that the shapes cannot always be routed away at 7/4 and that the least universal threshold-relative constant is 11/6.Source: §7 · p. 34
  • Excluding shape (O2) does not remove the 11/6 obstruction: the [1] family has no Step-2 job and still drives ALG/OPT to 11/6.This distinction applies to the polynomial-time algorithm; the exclusion can still help the best-matching variant.Source: §7 · p. 35
  • A seven-machine, six-job instance makes (R1) impossible for every valid matching, although each matching has makespan 1.The exhibited feasible point is not a vertex, so this example does not settle the vertex-restricted question.Source: §7 · pp. 35–36

8 The family the 7 4 bound is known to be tight against

The generalized three-path family is a relaxation extremal family, but every valid matching finishes at its optimum under the stated conditions. Its OPT/TLP ratio is strictly below 7/4 at every finite member and approaches 7/4 in the limit.

The family the 7/4 bound is known to be tight against.

9 What remains open

The remaining questions concern the best completion procedure, completion at a prescribed vertex solution, and the size of near-extremal vertex instances. The section also records the threshold-dependent guarantee and its best threshold choice.

9 What remains open

  • The best threshold choice is β = 2/3; lowering the threshold does not improve the guarantee and destroys it.The reported formulas give the guarantee on both scales above and at or below 1/2.Source: §9 · p. 40
  • For near-extremal vertex instances, the asymptotic machine-count question remains open, as does whether the construction’s constant is optimal.The passage also asks for the limiting lower constant in εN(ε).Source: §9 · p. 40
  • It remains open whether an instance and feasible threshold can be mapped in polynomial time to a feasible relaxation solution with minimum-makespan completion.The supplied-solution hardness result does not settle joint selection of the Step-1 solution and Step-3 matching.Source: §9 · p. 40
  • It is also open whether minimum-makespan completion is polynomial-time solvable when Step 1 is pinned to a vertex returned by a specified polynomial-time LP algorithm.The weak NP-completeness result leaves open pseudo-polynomial algorithms for bounded common denominators and fixed-parameter algorithms by machines or slots.Source: §9 · p. 40

10 What this note establishes

The note shows that optimizing the slot matching and restricting the relaxation solution to a vertex do not improve the scheme’s 11/6 worst-case constant. It also establishes limits on what can be concluded and identifies remaining open questions.

Section 10 What this note establishes

  • Both natural 7/4 claims fail: every matching finishes at least 44/25 against the threshold, while a different instance forces 85/48 against the optimum.The threshold result is at a least feasible T; the optimum-scale counterexample is given at g = 4.Source: §10 · p. 41
  • The minimum-makespan matching oracle still has worst-case ratio exactly 11/6 against the optimum, and no execution attains that supremum.Theorem 9 supplies the lower bound and Corollary 10 fixes the constant; Theorem 17 records unattainment.Source: §10 · p. 41
  • Restricting Step 1 to vertices does not help: for every g ≥ 2, every valid matching has load exactly 11/6 − 1/(4g), with T = OPT = 1.The vertex family binds every matching-selection rule, including randomized ones, and its ratio approaches 11/6 without attaining it.Source: §10 · p. 41
  • The note also confines overloads to two shapes, rules out the natural two-phase repair, and proves a strict 7/4 bound on the generalized three-path family.The three-path bound is its exact supremum.Source: §10 · p. 41
  • The size of a near-extremal vertex instance and the complexity of selecting one remain open.The note says the ceiling is strict at every feasible point, so no execution reaches 11/6.Source: §10 · p. 41
  • The note does not improve graph balancing’s approximation ratio, which remains 1.75.Source: §10 · p. 41

A Computational record

The computational record reports exact checks, enumerations, and sampled measurements supporting the paper’s constructions and claims. It distinguishes these measurements from proofs and notes where sampling or search does not approach the relevant bounds.

A Computational record

  • For g = 1,…,6, exact enumeration found the minimum and maximum valid-matching loads equal at 11/6 − 1/(4g), with the fifth instance reaching 107/60.The checks enumerate every valid matching at each parameter; the tie-break sweep covers all free orderings only through g = 5.Source: A Computational record · p. 42
  • A smaller 18-machine vertex instance reaches 37/21 > 7/4, showing that 43 machines are not required for this construction.Its vertex rank is 79 of 79; the check reports infeasibility at 7/4 and feasibility at the claimed value.Source: A Computational record · p. 43
  • The reported measurements are not proofs, and the note says none of them carries a statement on which its argument depends.The record also notes that the climb in g stopped at a recursion limit rather than a failure.Source: A Computational record · p. 43
  • The vertex searches certified 207 vertices in one pool, whose largest ratio was 17/12; four size bands produced a separate maximum of 7/6.The largest value from the bands was 4/3 in the first three and 7/6 in the fourth, so the searches are reported separately.Source: A Computational record · p. 43
  • The sampled per-machine checks found zero violations across 13,174 enumerated matchings, but the closest random samples remained below the tested bounds.The reported gaps are 7/36 below (S), 1/4 below (N1), and 5/12 below (N0); Theorem 6’s family approaches the ceiling more closely.Source: A Computational record · p. 43
  • A 2,000 × 1,200 grid measured a supremum of 1.75 for the closed form at (S, c) = (0.5, 0.25), but the form matches the truth only on r = 3, S = 1/2.The passage records this measurement as locating the extremal line, not as validating the form off it.Source: A Computational record · p. 44

Code and data

The paper deposits its claim-supporting scripts, artifacts, logs, and a driver in an Open Science Framework package. The deposit reproduces the reported numerical measurements except for one solver-behaviour fact.

Code and data

  • The OSF package includes claim-supporting scripts, artifacts, logs, pinned dependencies, and a driver with quick and full verification tiers.A README maps each claim to the command and artifact that establish it.Source: Code and data · p. 44
  • The deposit reproduces every reported numerical measurement except the solver-behaviour fact in Measurement 11, which has no regenerating script.The exploratory proof attempts and internal revision diary are not part of the replication set.Source: Code and data · p. 44

Authorship and computational process

The author reports using AI assistants for writing, adversarial review, and simulation work, while retaining responsibility for the paper and its claims.

Authorship and computational process

Loading 2609.10004v1…