we-solve (beta)

CS-433 · computer science · mathematics · Algorithms and data structures · Graph theory and combinatorics

Approximating Fare-Zone Assignment on Trees

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

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.

$y_e=1$ selects an edge as a fare-zone boundary. For a commodity path $P_i$, the constraint limits how many selected edges lie along it; the objective adds its weight once for each selected edge it traverses.

Statement recorded in the supplied source.
Given a tree $G=(V,E)$ and weighted commodity paths $(P_i,w_i,u_i)$, choose $y_e\in\{0,1\}$ to maximize $\sum_{e\in E}y_e\sum_{i:e\in P_i}w_i$ subject to $\sum_{e\in P_i}y_e\leq u_i$ for every $i$. What approximation guarantees are achievable on trees, particularly when the maximum number of paths sharing an edge is bounded by a parameter $k$? [S2]
Scope qualification.
The input includes the listed path weights and budgets; no omitted transit-network interpretation changes the displayed optimization problem.
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

Approximate the stated fare-zone optimization on trees, especially when few commodity paths share any edge.

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30006109 and source code OWR-14298804-012 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

CS-433-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-433

Approximating Fare-Zone Assignment on Trees

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.

$y_e=1$ selects an edge as a fare-zone boundary. For a commodity path $P_i$, the constraint limits how many selected edges lie along it; the objective adds its weight once for each selected edge it traverses.

Statement recorded in the supplied source.
Given a tree $G=(V,E)$ and weighted commodity paths $(P_i,w_i,u_i)$, choose $y_e\in\{0,1\}$ to maximize $\sum_{e\in E}y_e\sum_{i:e\in P_i}w_i$ subject to $\sum_{e\in P_i}y_e\leq u_i$ for every $i$. What approximation guarantees are achievable on trees, particularly when the maximum number of paths sharing an edge is bounded by a parameter $k$? [S2]
Scope qualification.
The input includes the listed path weights and budgets; no omitted transit-network interpretation changes the displayed optimization problem.
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

Approximate the stated fare-zone optimization on trees, especially when few commodity paths share any edge.

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30006109 and source code OWR-14298804-012 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Research attempt

Literature, source context and scope

The full catalogue body, including qualifications and historical source status, is preserved above. The original workshop report was inspected in the locally cached publisher PDF text. This attempt distinguishes the source question from any explicitly restricted model introduced below. Repeated records retain their own source IDs and do not become independent conjectures. Elementary results and attributed literature results are not claimed as new original-target progress.

Attempted bounded-congestion exchange route

We use the displayed hard-budget formulation, in the restricted but natural case of nonnegative rational path weights and nonnegative integer budgets. Delete any edge lying on a zero-budget path; those edges can never be selected. Put $c_e=\sum_{i:e\in P_i}w_i\ge0$ and assume the congestion bound $k\ge1$. Repeatedly select a highest-weight edge whose addition is feasible, until the selected set $A$ is inclusion-maximal. This is a polynomial-time greedy algorithm by checking the listed path budgets.
Proposition: The resulting weight is at least $1/k$ times the optimum weight.
Proof: Suppose $A\subseteq B$ are feasible and $A+e$ is feasible. Adding $e$ to $B$ violates at most $k$ budgets, since only paths containing $e$ can be violated. For each budget still violated, remove one edge of $(B\setminus A)\cap P_i$. Such an edge exists: $B$ already met that budget, its violation is by exactly one, and $A+e$ meets it. At most $k$ removals make $B+e$ feasible without deleting $A$. Start $B$ at an optimum $O$ and maintain a feasible $B$ containing the current greedy prefix. If the chosen $e$ is already in $B$, no exchange is needed; otherwise use the preceding removals and insert $e$. Every removed edge was individually feasible for addition to the previous prefix, hence has weight at most $c_e$. Charge its weight to $e$. An original optimum edge chosen while still in $B$ is charged to itself instead. These cases charge at most $k$ original optimum edges per greedy edge (at most one in the latter case). At termination, no unchosen edge can remain in $B$, because it could be added to the maximal greedy set. Thus every original optimum edge has been charged, and $c(O)\le k c(A)$. ∎
This is the standard elementary exchange argument for column-sparse cardinality packing, proved here to fix scope; no novelty or original-target completion is claimed. It does not use the tree structure beyond the congestion bound. The next attempted improvement is to round the natural LP as if it were integral. A star with three edges and a unit-weight, unit-budget path between every pair of leaves defeats that step. Each edge has weight two; the three pair constraints permit $(1/2,1/2,1/2)$, of value three, while an integer feasible solution chooses at most one edge, of value two. The tight-constraint matrix has determinant two, so the fractional point is an LP vertex.

Verification and remaining gaps

All eight binary choices for this star and the three tight LP constraints were checked. A better tree-specific approximation, optimal dependence on congestion, and stronger rounding remain unproved. The newer fare-zone paper cited by the catalogue uses dropout and pricing, which cannot silently replace this hard-budget problem.

References and source attribution

The primary Oberwolfach workshop report, https://doi.org/10.4171/owr/2024/50, was inspected on 11 October 2026. Relevant source passages: 2024/50 p. 2992, hard-budget fare-zone formulation. Catalogue and contributor attribution remain in the original Sources section. Mathematical arguments labeled as this attempt are proved above; cited external results remain attributed to their authors and are not independently reproved or claimed as our discoveries.

https://arxiv.org/html/2512.19493v3. Hoefer, Kauther, Pabst, Peis and Tran, Fare Zone Assignment on Trees, version 3. The model definition was inspected: commodities may drop out when budgets are exceeded, and revenue uses a subadditive pricing function. This differs from the report constraints requiring every budget to hold. Its approximation results are therefore not transferred here without a proved correspondence.

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% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch011/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

Go to contribution →