last day (15 days later) » 

Stack Exchange
Stack Exchange
20:11
2
Q: Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs

iheapOrlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question. If the graph $G(V = V_1 \cup V_2, E)$ is known...

ds.algorithms graph-algorithms max-flow
iheap
iheap
@usul: Yes, the source connects to one side of the graph, and the sink the other. I changed the question text to clarify this point. Also, all costs are non-negative. Thanks!
Saeed
Saeed
O(1) or exactly 1? for example if all of them are 2 we can assume all are one and this is differ from O(1).
iheap
iheap
@Saeed: For any algorithm whose time complexity depends on $c$ and $w$, you can substitute $1$ for these two numbers in the big-O expression. Note that the graph might have unlimited capacity edges; i.e. the number $c$ is the maximum finite capacity.
Saeed
Saeed
@iheap, I think maybe it's better to read my answer then teach me. not all algorithms are relying on c. but if all capacities are c then there are free to use algorithms which I mentioned one of them in my answer (modified dinic algorithm), but if you want to use them e.g with capacities in {1,2} then you have to modify those algorithms and I don't know if modification is trivial. But why I asked this? 1. because of ur previous question that I commented and answer and that needs flow on unit capacity graph. 2. Your choice of algorithm as you wrote in your question it's a little bit strange.
iheap
iheap
@Saeed: I wasn't trying to teach you anything, I was just trying to clarify things for everybody's (including myself) benefit. No need to get defensive. I see where you are coming from (i.e. relating the other question and this), but they are really two separate questions.
@Saeed: I started the discussion with Orlin's 1991 algorithm, because it is cited as the "fastest" algorithm known for this purpose in a (apparently outdated) textbook that I had. At this point in the discussion, it is obvious that it is not the best way to go under my assumptions.
Saeed
Saeed
20:11
OK I understand that they are not related but still note that weight 1 and weight in {1,2} are not simply convertible. e.g TSP is trivial if all weights are 1 but npc if weights are {1,2}, this is an strange example but it says it's not easy to say that if for capacity c we have solution then for capacity in {1,...,c} we have solution with same running time.p.s: anyhow ford falkerson is even older, I see that you didn't notice your conditions carefully.
iheap
iheap
You are right, $c = 1$ and $c = O(1)$ are definitely not the same. In this question, it is the latter.
Saeed
Saeed
yeah, I think I'm right in general but I'm not pretty sure about those flow algorithms. e.g in ford falkerson algorithm they are same. I think even in dinic's algorithm they are almost same while we are using real capacities.
iheap
iheap
Hello Saeed. I did not want to clutter the comment section, so I am going to write here. Even if we had c = 1 exactly, would Dinic's algorithm still run in O(sqrt(n)*m) time? Since we have unlimited capacity edges in the graph, wouldn't that make Dinic's algorithm not as efficient?
 
2 hours later…
Saeed Amiri
Saeed Amiri
22:19
if both costs and capacities are 1,sure modified version of dinic works. that modified dinic algorithm known as hopcroft algorithm, take a look if you want. One may improve that algorithm till now. en.m.wikipedia.org/wiki/Hopcroft–Karp_algorithm
also to ping someone use @iheap, I saw this randomly.
iheap
iheap
22:59
@SaeedAmiri: I couldn't find a reference that explains how Dinic's algorithm can be used to find minimum cost maximum flows. Can you give a reference that I can read? Thanks!
All references I found are concerned with finding the maximum flow, without considering the costs.

  last day (15 days later) »