ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G=(V,A)G=(V,A) be a directed graph with a distinguished source s∈Vs\in V, a set of terminals T⊆VT\subseteq V, and a demand dt≥0d_t\geq 0 for each t∈Tt\in T. A flow x=(xa)a∈Ax=(x_a)_{a\in A} with xa≥0x_a\geq 0 is called feasible (splittable, or fractional) for this instance if it satisfies flow conservation and routes dtd_t units from ss to tt for every t∈Tt\in T simultaneously; that is, xx is a nonnegative combination of ss–tt path flows whose total value into each terminal tt equals dtd_t, with each demand possibly divided among several paths. A flow yy is called unsplittable if there is a choice of a single ss–tt path PtP_t for each t∈Tt\in T such that

ya=∑t∈T: a∈Ptdtfor every a∈A,y_a=\sum_{t\in T:\ a\in P_t} d_t \qquad \text{for every } a\in A,

so that the entire demand of each terminal travels along one path. Put dmax⁡=max⁡t∈Tdtd_{\max}=\max_{t\in T} d_t.

For every such instance, every fractional flow xx feasible for it, and every cost vector c=(ca)a∈Ac=(c_a)_{a\in A} with ca≥0c_a\geq 0 for all a∈Aa\in A, there exists an unsplittable flow yy satisfying the same demands such that

ya≤xa+dmax⁡for all a∈A,and∑a∈Aca ya  ≤  ∑a∈Aca xa.y_a\leq x_a+d_{\max}\quad \text{for all } a\in A, \qquad\text{and}\qquad \sum_{a\in A} c_a\, y_a \;\leq\; \sum_{a\in A} c_a\, x_a.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.