Tagged Questions
0
votes
1answer
227 views
Multicommodity flow in polynomial size
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 ...
1
vote
1answer
62 views
Does the sparsest cut always have a solution?
How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset?
It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't ...
2
votes
1answer
99 views
Sparsest cut is solvable on trees
The problem is to prove that Sparsest cut is solvable on trees in polynomial time.
A short review, a sparsest cut is linear program
$$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$
where ...
4
votes
1answer
114 views
Book on advanced topics of Network Flows
I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
1
vote
1answer
376 views
What is the restriction matrix used for in the stepping stone method?
Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1...m, demand nodes ...
