Proved
Original congestion-only theorem ↗
No cost-preservation assertion.
Source dated Aug 4, 2023 · Observed Oct 13, 2026
Theorem · version 1
The original congestion guarantee
Statement
For every feasible rational single-source fractional flow x there exists a polynomial-time computable unsplittable routing P with load_P(a) ≤ x(a) + d_max for every arc.
Assumptions
- Finite single-source directed network and feasible nonnegative fractional flow.
- All terminals are routed with their whole demands on single paths.
Scope
Dinitz–Garg–Goemans’ theorem provides congestion control without promising the same cost.
Evidence
Source reports
Connections
In this problem · publication v8 · Selected context
Cost-preserving unsplittable flow →
Supporting result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v9
Cost-preserving unsplittable flow →
Supporting result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Single-Source Unsplittable Flows in Planar Graphs →
- Definition 1.1, Theorem 1.2, Conjecture 1.3 and Theorem 1.8 → · Original passage ↗
Recorded wording
The paper states the original congestion theorem, Goemans’ cost-enhanced conjecture and a planar theorem with twice the largest-demand allowance.
paraphrase · OpenMath supplies its own mathematical paraphrases and links; proof text is not republished.
Vera Traub · Laura Vargas Koch · Rico Zenklusen · Preprint · Publication date Aug 4, 2023
Revision & attribution
Source revision: 2023-08-04. Observed Oct 13, 2026.
No specific AI contribution is attributed by this source record.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Original congestion-only theorem ↗
No cost-preservation assertion.
Source dated Aug 4, 2023 · Observed Oct 13, 2026 · Source passage →
Record details
- Claim ID
- claim-flow-congestion-only-rounding
- Statement version
- 1
- SHA-256
- 273445310248d342b860e2c6609107d1aaa7ba5ed115a348a15064dc74c27352