Minimum-Cost Flow: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
V: number of vertices | $V$: number of vertices | ||
E: number of edges | $E$: number of edges | ||
U: maximum edge capacity | $U$: maximum edge capacity | ||
d: minimum required flow | $d$: minimum required flow | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 30: | Line 30: | ||
| [[Dinitz ( Maximum Flow)|Dinitz]] || 1970 || $O(V^{2}E)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Dinitz ( Maximum Flow)|Dinitz]] || 1970 || $O(V^{2}E)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Edmonds & Karp ( Maximum Flow)|Edmonds & Karp]] || 1972 || $O(E^{2} | | [[Edmonds & Karp ( Maximum Flow)|Edmonds & Karp]] || 1972 || $O(E^{2} \log U)$ || $O(E)$ || Exact || Deterministic || [https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Karzanov ( Maximum Flow)|Karzanov]] || 1974 || $O(V^{3})$ || $O(V^{2})$ || Exact || Deterministic || [http://alexander-karzanov.net/Publications/maxflow-acyc.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Karzanov ( Maximum Flow)|Karzanov]] || 1974 || $O(V^{3})$ || $O(V^{2})$ || Exact || Deterministic || [http://alexander-karzanov.net/Publications/maxflow-acyc.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Galil & Naamad ( Maximum Flow)|Galil & Naamad]] || 1980 || $O( | | [[Galil & Naamad ( Maximum Flow)|Galil & Naamad]] || 1980 || $O(VE \log^{2} V)$ || $O(E)$ || Exact || Deterministic || [https://core.ac.uk/download/pdf/81946904.pdf Time & Space] | ||
|- | |- | ||
| [[Dantzig ( Maximum Flow)|Dantzig]] || 1951 || $O(V^{2}EU)$ || $O(VE)$? || Exact || Deterministic || | | [[Dantzig ( Maximum Flow)|Dantzig]] || 1951 || $O(V^{2}EU)$ || $O(VE)$? || Exact || Deterministic || | ||
|- | |- | ||
| [[Dinitz (with dynamic trees) ( Maximum Flow)|Dinitz (with dynamic trees)]] || 1973 || $O( | | [[Dinitz (with dynamic trees) ( Maximum Flow)|Dinitz (with dynamic trees)]] || 1973 || $O(VE \log U)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] | ||
|- | |- | ||
| [[Cherkassky ( Maximum Flow)|Cherkassky]] || 1977 || $O(V^{2}E^{0.5})$ || $O(E)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/abs/pii/S037722179600269X Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Cherkassky ( Maximum Flow)|Cherkassky]] || 1977 || $O(V^{2}E^{0.5})$ || $O(E)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/abs/pii/S037722179600269X Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Sleator & Tarjan ( Maximum Flow)|Sleator & Tarjan]] || 1983 || $O( | | [[Sleator & Tarjan ( Maximum Flow)|Sleator & Tarjan]] || 1983 || $O(VE \log V)$ || $O(E)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0022000083900065 Time] | ||
|- | |- | ||
| [[Goldberg & Tarjan ( Maximum Flow)|Goldberg & Tarjan]] || 1986 || $O( | | [[Goldberg & Tarjan ( Maximum Flow)|Goldberg & Tarjan]] || 1986 || $O(VE \log (V^{2}/E))$ || $O(E)$ || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf Time] | ||
|- | |- | ||
| [[Ahuja & Orlin ( Maximum Flow)|Ahuja & Orlin]] || 1987 || $O(VE + V^{2} | | [[Ahuja & Orlin ( Maximum Flow)|Ahuja & Orlin]] || 1987 || $O(VE + V^{2} \log U)$ || $O(ELogU)$ || Exact || Deterministic || [https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem Time] | ||
|- | |- | ||
| [[Ahuja et al. ( Maximum Flow)|Ahuja et al.]] || 1987 || $O(VELog(V(LogU)$^{0.5} / E)) || || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf Time] | | [[Ahuja et al. ( Maximum Flow)|Ahuja et al.]] || 1987 || $O(VELog(V(LogU)$^{0.5} / E)) || || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf Time] | ||
Latest revision as of 08:18, 10 April 2023
Description
Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, each edge is given a cost coefficient, and we wish to minimize total cost while reaching a threshold flow.
Related Problems
Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity
Parameters
$V$: number of vertices
$E$: number of edges
$U$: maximum edge capacity
$d$: minimum required flow
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Ford & Fulkerson | 1955 | $O(E^{2}U)$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Dinitz | 1970 | $O(V^{2}E)$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Edmonds & Karp | 1972 | $O(E^{2} \log U)$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Karzanov | 1974 | $O(V^{3})$ | $O(V^{2})$ | Exact | Deterministic | Time & Space |
| Galil & Naamad | 1980 | $O(VE \log^{2} V)$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Dantzig | 1951 | $O(V^{2}EU)$ | $O(VE)$? | Exact | Deterministic | |
| Dinitz (with dynamic trees) | 1973 | $O(VE \log U)$ | $O(E)$ | Exact | Deterministic | Time |
| Cherkassky | 1977 | $O(V^{2}E^{0.5})$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Sleator & Tarjan | 1983 | $O(VE \log V)$ | $O(E)$ | Exact | Deterministic | Time |
| Goldberg & Tarjan | 1986 | $O(VE \log (V^{2}/E))$ | $O(E)$ | Exact | Deterministic | Time |
| Ahuja & Orlin | 1987 | $O(VE + V^{2} \log U)$ | $O(ELogU)$ | Exact | Deterministic | Time |
| Ahuja et al. | 1987 | $O(VELog(V(LogU)$^{0.5} / E)) | Exact | Deterministic | Time | |
| MKM Algorithm | 1978 | $O(V^{3})$ | $O(E)$ | Exact | Deterministic | Time & Space |
| Galil | 1978 | $O(V^({5}/{3})$E^({2}/{3})) | $O(E)$ | Exact | Deterministic | Time & Space |
| Shiloach | 1981 | $O(V^{3}*log(V)$/p) | $O(E)$ | Exact | Parallel | Time |
| Gabow | 1985 | $O(VE*logU)$ | $O(E)$ | Exact | Deterministic | Time |
| Lee, Sidford | 2014 | $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) | $O(E)$ | Exact | Deterministic | Time |
| Madry | 2016 | $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) | $O(E)$ | Exact | Deterministic | Time |
| Kathuria, Liu, Sidford | 2020 | $O(E^({1}+o({1})$)/sqrt(eps)) | $O(E)$ or $O(V^{2})$ ? | 1+eps | Deterministic | Time |
| Kathuria, Liu, Sidford | 2020 | $O(E^({4}/{3}+o({1})$)U^({1}/{3})) | $O(E)$ or $O(V^{2})$ ? | Exact | Deterministic | Time |
| Brand et al | 2021 | $O((E+V^{1.5})$log(U)polylog(V, E, log U)) | $O(E)$ | Exact | Randomized | Time |
| Gao, Liu, Peng | 2021 | $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) | $O(E)$ | Exact | Deterministic | Time |
| Chen et al | 2022 | $O(E^({1}+o({1})$)*log(U)) | $O(E)$ | Exact | Deterministic | Time |