0
votes
1answer
30 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
1
vote
1answer
54 views

Enquiry to network flow

Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear ...
0
votes
1answer
46 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
1answer
319 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
71 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
133 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
177 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
499 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 ...