Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# - Approximation Schemes for Fractional Multicommodity Flow Problems

DOI link for - Approximation Schemes for Fractional Multicommodity Flow Problems

- Approximation Schemes for Fractional Multicommodity Flow Problems book

# - Approximation Schemes for Fractional Multicommodity Flow Problems

DOI link for - Approximation Schemes for Fractional Multicommodity Flow Problems

- Approximation Schemes for Fractional Multicommodity Flow Problems book

Click here to navigate to parent product.

## ABSTRACT

Flow problems are the basis of many optimization problems. Their eﬃcient solution has been studied intensively ever since the breakthrough treatise by Ford and Fulkerson [1] established the ﬁeld of network ﬂows and introduced novel algorithmic ideas for calculating them (such as the famous Ford-Fulkerson augmenting paths algorithm, and the modeling of dynamic ﬂows as static ones). Usually the input to such a problem consists of a directed network modeled as a graph G = (V, E), an edge capacity function u : E → R+ and a source-sink pair (s, t) (single commodity ﬂow) or, more generally, a set of k source-sink pairs (si, ti), 1 ≤ i ≤ k (multicommodity ﬂow). We want to calculate flows f i from si to ti that would optimize an objective function, subject to ﬂow conservation, and the constraint that the sum of ﬂows through an edge cannot exceed the capacity of the edge. Each origin-destination pair (and its corresponding ﬂow f i) is usually called a commodity. More formally, given the graph G, the edge capacities u, and the k source-sink pairs above, the ﬂows f i : E → R+ for i = 1, . . . , k must satisfy the following sets of constraints: Capacity constraints: For all edges e ∈ E, we require ∑ki=1 f i(e) ≤ u(e). Flow conservation: For all commodities i = 1, . . . , k, and for all vertices u ∈ V \ {si, ti}, we require ∑

v:(v,u)∈E f i(v, u) =

v:(u,v)∈E f i(u, v).