Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size?

Linear program of multicommodity flow

$maximize \space \sum_{p\epsilon P}^{ } {f_{p}}$

$subject \space to \space$

$\sum_{p:e\epsilon P}^{ } {f_{p}} \leq c_{e}, e \epsilon E$

$f_{p} \geq 0, p \epsilon P$

This formulation has exponentially many variables.

The dual LP problem to multicommodity flow is sparsest flow, which is can be formulated in polynomial size by using metrics

$minimize \space \sum_{e\epsilon E}^{ } {c_{e}d_{e}}$

$subject \space to$

$\sum_{u,v \epsilon V}^{ } {d_{v,u}} \geq 1$

$d_{v,w} \leq d_{v,r}+d_{r,w} \space \forall v,u,r \epsilon V$

$d_{v,r} \leq d_{v,w}+d_{w,r} \space \forall v,u,r \epsilon V$

$d_{w,r} \leq d_{w,v}+d_{v,r} \space \forall v,u,r \epsilon V$

$d_{v,w} \geq 0 \space \forall v,u \epsilon V$

where,

$c_{e}$ - capacity of the edge $e$

$d_{e} = 1$ iff $e$ is in $s-t$ cut

I suspect we can use metric to formulate multicommodity problem in polynomial size too. But right now it's not obvious to me.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

There seems to be some small confusion here. Your primal is the path-flow formulation of the multicommodity flow problem, which orders separate path-flow to every path in some given path set $P$ (which in turn can be of exponential size), while your dual is in fact the dual linear program corresponding to the arc-flow formulation (and hence has polynomial number of variables). Wikipedia has the arc-flow primal you want here and here is a nice intro.

share|improve this answer
    
Thanks for pointing this out! Is there any textbook in the field you would recommend? –  com Dec 16 '11 at 8:17
    
My all time favorite is Bazaraa, Jarvis, Sherali: Linear Programming and Network Flows, an extremely readable textbook on network flow theory (although a bit laconic on multicommodity flows). –  Gabor Retvari Dec 19 '11 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.