# Questions tagged [multicommodity-flow]

The tag has no usage guidance.

13 questions
141 views

### Anyone recognize this as a special type of multi-commodity flow problem?

Consider this problem:  \begin{align} \min_{y,z,l \geq 0} \quad & g(y,z,l) := \sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} & \\ \textrm{s.t.} \quad & \left( \sum_{(i,j)\in E} y_{ijp} + ...
720 views

### Minimum vertex k-cut

Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at ...
173 views

### Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
565 views

### Can the optimal minimum cost two-commodities flow be fractional on this special case?

Suppose that we have a two commodities flow network $N=<G=(V,E), s_1,s_2,t_1,t_2\in V>$. The problem is to find a minimum cost two-commodity flow in which there a flow $f_1$ from $s_1$ to $t_1$ ...
346 views

### Maximum matching versus preferential assignment

There are several ways to solve the marriage problem. The "preferential assignment" approach consists in forming couples on the basis of preferred characteristics expressed by each individual. An ...
477 views

### Another Solution Problem (ASP) of integer multi-commodity flow: is it NP-complete?

I know that integer multicommodity flow is NP-complete. It was proven in On the complexity of time table and multi-commodity flow problems that any SAT problem can be reduced to an integer ...
48 views

### Approximating BLEDP on restricted graph classes

In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of ...
187 views

### How can we derive this lower bound of a special cut in a graph?

I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
208 views

### Finding the perfomance ratio in a multicommodity-flow

I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are ...
207 views

### On the optimal solution of the CKR formulation for MULTIWAY CUT

Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR . Let $U_i$ be those vertices in $V-T$ which is ...
249 views

### Request for references on multicommodity flow-cut results

This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...