Better Approximations for Unrelated Graph Balancing

Unrelated graph balancing: exact unit-load feasibility and an unbounded cheap-endpoint trap

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

In unrelated graph balancing, every edge $e=uv$ is assigned to one endpoint, with load $p_{e,u}$ or $p_{e,v}$ depending on that choice. The load at a vertex is the sum of loads assigned to it. The objective is to minimize the maximum vertex load. A simple graph has no parallel edges or loops; the restricted instance has $p_{e,v}\in\{1,k\}$ for each allowed endpoint, with fixed $k$.

Statement recorded in the supplied source.

Does unrelated graph balancing admit an approximation factor below $2$, even for simple graphs in which every orientation-dependent edge weight belongs to $\{1,k\}$ for a fixed $k$? [S2]

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Orient weighted jobs to their endpoints while beating a factor-two approximation of maximum load.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004913 (OWR-8415356-024). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Combinatorial Optimization, Oberwolfach Reports 53/2021, primary report PDF https://ems.press/content/serial-article-files/46931. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Does unrelated graph balancing admit an approximation factor below $2$, even for simple graphs in which every orientation-dependent edge weight belongs to $\{1,k\}$ for a fixed $k$?

The natural load-assignment route

The source allows different processing times at the two endpoints, including the restricted set $\{1,k\}$. We give a complete unit-load feasibility algorithm and then test the tempting extension of simply choosing each cheaper endpoint. The latter fails arbitrarily badly even for a fixed $k$ on simple graphs.

Unit loads reduce exactly to matching.

Suppose every allowed endpoint assignment has load one, and ask whether maximum load at most an integer $B\ge0$ is possible. Create one job node for each edge, and $B$ slot nodes for each graph vertex. Join a job to every slot of each endpoint to which it is allowed to be assigned. A matching covering all job nodes is equivalent to a feasible orientation: a matched slot chooses the endpoint and distinct slots ensure at most $B$ jobs there. Conversely assign distinct local slots to the jobs of every feasible orientation. The graph has at most $|V|B+|E|$ nodes. One never needs $B>|E|$, because assigning all edges arbitrarily uses no more than $|E|$ jobs at any vertex.

For completeness, a covering matching can be found or its absence certified by augmenting paths. Start with the empty matching. Search from an unmatched job, alternating unused job-slot edges and matched slot-job edges. If a free slot is reached, reverse membership of the path edges, increasing the matching by one. If no unmatched job has such a path but a larger matching existed, the symmetric difference of the two matchings would have components that are alternating paths or cycles (each vertex has degree at most two). Since the larger matching has more edges, one path has one more edge of it than of the current matching; it begins and ends at vertices unmatched by the current matching, giving an augmenting path. This contradiction proves maximal size and correctness. There are at most $|E|$ augmentations and each search scans a polynomial-size graph, so the algorithm is polynomial. Binary search over $B=0,\ldots,|E|$ gives the exact unit-load optimum.

A valid restricted extension below the heavy-job threshold.

For processing times in $\{1,k\}$, any proposed makespan $B<k$ forbids assigning an edge to an endpoint where it takes time $k$. Delete those choices and apply the preceding unit-load test with capacity $\lfloor B\rfloor$. This is an exact feasibility procedure for this threshold range. It does not address the general regime $B\ge k$, where heavy assignments can occur and consume $k$ units of capacity rather than one slot.

Choosing every cheap endpoint has unbounded ratio.

Fix an integer $k\ge2$ and take a star with $t\ge k$ leaves. Each edge takes time one at the center and time $k$ at its own leaf. The graph is simple and all processing times are in the prescribed two-value set. Choosing the cheaper endpoint for each edge assigns all $t$ jobs to the center, with makespan $t$. Assigning every edge to its leaf gives makespan $k$. No solution has makespan below $k$: if any edge goes to a leaf it alone creates load $k$, while if none does the center has load $t\ge k$. Thus the optimum is exactly $k$ and the cheap-endpoint ratio is $t/k$, unbounded with $t$ even though $k$ is fixed.

The same example explains why minimizing total processing time is not a substitute for minimizing maximum load. The unique minimum total-time assignment uses all cheap center endpoints and has total $t$, yet the balanced solution with maximum load $k$ has total $kt$. Total-time optimality contains no constant-factor makespan conclusion here.

Audit and missing general step

The primary question and the two-value discussion on printed pages 2947--2948 were inspected. The audit retained endpoint-dependent weights, simplicity of the graph, fixed $k$, and the distinction between makespan and total load. The slot construction is a known matching mechanism, proved here to mark its exact range; heavy jobs cannot be replaced by one unit slot. No matching implementation, LP computation or configuration-gap claim was made. Handling the joint placement of heavy and light jobs with a uniform approximation below two remains unresolved here.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. Exact unit-load and below-k feasibility are proved, but the unrestricted two-value case is not solved and cheap-endpoint assignment has an unbounded ratio.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. Exact unit-load and below-k feasibility are proved, but the unrestricted two-value case is not solved and cheap-endpoint assignment has an unbounded ratio.