Exact Locality Gaps for Matchable Semi-Matchings

1 Introduction

• In the three-task example, no single eligible move lowers cost, but moving two tasks together reduces the total from four to three, attaining the 4/3 single-move bound at load cap two.The eligibility pattern gives the first task one server, the second two choices, and the third two choices.Source: §1 · pp. 1–2
• The assignment objective sums each server's triangular load cost, and the locality gap compares a locally optimal assignment's cost with the global optimum.Matchability means a matching covers every client, so a distinct-server assignment is feasible.Source: §1 · p. 2

1.1 Our results and proof method

• Excluding improving paths that move at most r clients is equivalent to excluding every improving feasible reassignment of at most r clients.This sharpens the cited 1 + 1/r guarantee of Czygrinow et al. on matchable instances.Source: §1 · p. 2
• For every move radius r and maximum load K, the paper gives an exact locality-gap formula, with finite-cap values attained by trees where each client has at most two choices.At K = 2, a path with r + 2 clients attains 1 + 1/(r + 2); without a load cap, the excess above one is 1/(r + 2) + O(2^-r/r).Source: §1.1 · p. 2
• The proof compares an assignment with a client-covering matching, assigns rational potentials to comparison-graph states, and uses layered trees to attain the bound.The comparison graph includes directed cycles and self-loops, and the argument is finite for every r and K.Source: §1.1 · p. 2

1.2 Related work

• Prior work studies latency games, potential certificates, and other scheduling neighborhoods; the paper's contribution is a radius-dependent certificate and matching extremal family for its class.Related settings include linear-latency load-balancing games, congestion-game certificates [4], and single-job scheduling moves [7].Source: §1.2 · pp. 2–3
• The theorem assumes matchability; instances whose optimum requires a server load above one lie outside its scope.The matching assumption is central to constructing the comparison graph.Source: §1.2 · p. 3

2 Model and exact statement

• A matchable instance has a client-covering matching, so its optimum total completion cost is n; the locality gap compares a locally optimal assignment’s cost with that optimum.The assigned-load cap K bounds current server load, not graph degree.Source: §2 · p. 3
• An assignment is r-non-swappable exactly when no feasible reassignment changing at most r clients lowers total cost.The proof represents changed clients as arcs between their old and new servers, then decomposes these into cycles and donor-to-receiver paths.Source: §2 · p. 3
• For every r and finite cap K ≥ 2, the locality-gap value is attained by a finite eligibility tree with client degree at most two and server degree at most K.The result also states that the unrestricted-load supremum is approached by finite tree constructions as K grows, but is not attained by any finite instance.Source: §2 · p. 4
• The proof obtains the unrestricted-load result by taking suprema over load caps, with a finite argument for each r and K.The comparison is between total completion cost and the optimum on the matchable class.Source: §2 · pp. 3–4

3 One-parent comparison graphs

• A matching covering all clients and every currently loaded server is built by selecting one assigned client per loaded server, then augmenting to a maximum matching.The augmentation preserves coverage of already covered servers, and matchability ensures the maximum matching covers all clients.Source: §3 · p. 4
• Each client links its current server to its matched server, yielding a directed comparison graph in which every server has a unique parent, including on cycles.Self-loops are retained.Source: §3 · p. 4
• Every directed walk of at most r arcs obeys the load bound that its starting server’s load is at most the endpoint load plus one.A violation would yield a shorter simple alternating path contradicting r-non-swappability.Source: §3 · p. 5
• A server state records its load and, when present, the distance-based coordinate of its nearest recent ancestor with load one higher.When no such ancestor occurs within the specified window, the second coordinate is zero.Source: §3 · p. 5
• Allowed transitions account for a one-unit load drop with a reset coordinate, a same-load step with a decreasing coordinate, or an increase with a reset.Load-zero states have no outgoing arcs; the transition reasoning also applies to cycles and self-loops.Source: §3 · p. 5

4 A finite rational potential certificate

• A state potential satisfying the transition inequalities and a separate zero-load bound yields C(M) ≤ R OPT(G) by summing over the comparison graph.Every vertex occurs once as an arc target, so the potential terms cancel; the potentials need not be nonnegative.Source: §4 · p. 5

4.1 Identities and monotonicity

• The potential identities give recurrence relations across state coordinates, while monotonicity makes potentials nonincreasing in the second coordinate.The construction uses rational values formed from finite sums.Source: §4 · p. 6, §4.1 · p. 6

4.2 Verification of every transition

• The certificate is checked for each allowed transition type; for r = 1, a separate monotonicity argument handles the case without using an invalid index.The criterion also covers K = 1 separately, where each client contributes exactly one to the cost and the gap is 1.Source: §4.2 · p. 7

5 Finite constructions attaining the bound

• Each non-top server receives movable clients from the layer below, while the top server keeps one fixed client; moving all movable clients down yields a client-covering matching.Every client has degree at most two, and the resulting eligibility graph is a tree.Source: §5 · p. 8
• No improving move of at most r clients exists, but a path from layer r + 1 to layer zero takes r + 1 moves and lowers endpoint load by two.Thus the radius condition is substantive in the construction.Source: §5 · p. 8
• The layered construction proves the matching lower bound and finite attainment of the finite-cap formula.Its eligibility graph is a tree, and the construction supports exact guarantees under server-degree and whole-graph degree bounds.Source: §5 · pp. 8–9

5.1 Two concrete special cases

• For load cap two, a path with r + 2 clients attains the exact gap 1 + 1/(r + 2), with degree at most two at every client and server.The same construction gives the leading term of the unrestricted-load answer.Source: §5.1 · p. 9
• The explicit example has 79 clients and 79 servers, cost 96, and optimum 79, yielding a ratio of 96/79; the cited passage does not specify r or K.Its shortest improving path moves four clients.Source: §5.1 · p. 9

6 Unrestricted loads and dependence on the radius

• For fixed r, the finite-cap expression strictly increases with K, while no finite instance attains the unrestricted-load value βr.Every finite assignment has a finite maximum load, so its ratio is bounded by a finite-cap value.Source: §6 · p. 9
• For fixed r, the series Er and Tr converge absolutely; as r grows, their factorial-decay expansions begin Er = 2^-r + O(6^-r) and Tr = 2^-r/2 + O(6^-r).The text substitutes these expansions into the exact difference formula for the unrestricted-load bound.Source: §6 · pp. 9–10
• The unrestricted-load bounds βr strictly decrease with r, and β1 = 3/2.At r = 1, the series terms are E1 = e − 2 and T1 = 3 − e.Source: §6 · p. 9

7 Computational verification and code availability

• The code and generated data are publicly available in the cited repository, with exact checks using Python and rational arithmetic.The manuscript version is identified as commit a04c888.Source: §7 · p. 10
• The main script checks 108 exact potential certificates covering 17,730 transition inequalities and 108 compressed layered constructions.It also verifies five explicit graphs and ten rational intervals of width below 10^-30 for infinite-load constants.Source: §7 · p. 10
• An independent enumeration checks 20,274 stable graph/parameter cases for r = 1, . . . , 4 against the formula.It exhausts the stated parent-map family on one through six servers, not all bipartite eligibility graphs; these computations supplement the symbolic proof.Source: §7 · p. 10

8 Concluding remarks

• Excluding short improving paths gives more precise guarantees than the general 1 + 1/r bound on matchable instances.Finite-cap worst cases are attained on trees with client degree at most two, while the leading large-radius term is attained on paths.Source: §8 · p. 10
• An optimum with load above one creates comparison graphs with larger indegrees, so the present ancestor state does not apply directly.The distributed complexity of finding assignments satisfying the radius condition is a separate open question.Source: §8 · p. 11

• The research received no specific grant from funding agencies in the public, commercial, or not-for-profit sectors.Source: Funding · p. 11

• ChatGPT assisted with verification-code development and checking and with mathematical and editorial preparation of the LATEX manuscript.Source: Declaration of generative AI and… · p. 11
• The authors reviewed and revised the output and take full responsibility for the results, proofs, and final text.Source: Declaration of generative AI and… · p. 11