Talk:Maximum flow problem

Missing equations/images

Fairness in car sharing (carpool) subsection mentions some equations and images, but those are missing. Iomartin (talk) 11:34, 20 July 2015 (UTC)

Solution

The picture MFP2.jpg is wrong and it is an erroneous plagiarism of a copyrighted picture: See [1] — Preceding unsigned comment added by 131.188.224.200 (talk) 09:53, 21 November 2011 (UTC)

Diagram 4.4.1 Max flow with vertex capacities ==

i think this diagram is wrong it is doing the opposite to what is being described in the text Vin and vout should be swapped — Preceding unsigned comment added by Spartan3123 (talk • contribs) 00:50, 7 November 2011 (UTC)

Real world example

I'd like to see some examples of problems that can be solved by turning them into Maximum flow problems. Joepnl (talk) 16:53, 8 October 2010 (UTC)

What does "integral capacity" mean?

And what does it mean that there exists an integral maximum flow? Velle (talk) 23:57, 27 January 2011 (UTC)

It means that edge capacities and flow values are integers. -- X7q (talk) 01:05, 28 January 2011 (UTC)

History

The history section is severely flawed. The referenced papers do not support the claim that Dantzig created the max flow problem or that it was used in the Berlin airlift. The cited papers refers to the transportation problem. The referenced textbook (CLRS) does not acknowledge Dantzig as the creator of the max flow problem. The only reference to the Berlin airlift is an MIT press release (and its echos). I would view Schrijver's peer-reviewed article as authoritative.

Schrijver, Alexander, "On the history of the transportation and maximum flow problems", Mathematical Programming 91 (2002) 437-445

Moreover, the 2010 electric flow result is a significant result, but it is misleading to single it out in the history section (e.g., instead of Edmonds-Karp or other classic results). —Preceding unsigned comment added by 128.112.139.195 (talk) 10:36, 18 April 2011 (UTC)

Minimum path cover in directed acyclic graph

First of all, the minimum path cover in DAG problem is not an application of max flow. It is an application of maximum bipartite matching and should be moved to that page. Also I believe it's better to express this application using Dilworth's theorem. — Preceding unsigned comment added by Mizgly (talk • contribs) 19:30, 5 December 2012 (UTC)

It is noteworthy to differentiate between a "path cover" and a "vertex-disjoint path cover". The current section only applies to the vertex-disjoint case. A counter-example being 1->2->4, 3->2->5. 141.3.49.88 (talk) 16:15, 27 April 2015 (UTC)

Carpool example

I removed the following example, as it is half-baked and makes reference to a non-existent figure. Perhaps someone could flesh it out and add it back in?

Fairness in car sharing (carpool)

The problem exactly is that $N$ people are pooling a car for $k$ days. Each participant can choose if he participates on each day. We aim to fairly decide who will be driving on a given day.
The solution is the following:
We can decide this on the basis of the number of people using the car i.e.; if $m$ people use the car on a day, each person has a responsibility of $1/m$. Thus, for every person $i$, his driving obligation $D_{i}$ as shown. Then person $i$ is required to drive only $[D_{i}]$ times in $k$ days.
Our aim is to find if such a setting is possible. For this we try to model the problem as a network.
Now, it can be proved that if a flow $k$ exists then such a fair setting exists and such a flow of value $k$ always exists.

Doctormatt (talk) 00:03, 28 August 2015 (UTC)

Update Table with known results

One should update the table that lists the best known algorithms for computing the maximum flow. To the best of my knowledge the best current algorithm is Madry's algorithm running in time O(m^(10/7) polylog(m)). The paper of the algorithm is called "Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back" and can be found here: https://people.csail.mit.edu/madry/docs/matching_flow.pdf --131.130.117.228 (talk) 17:04, 18 January 2016 (UTC)

Note however that Madry's algorithm only applies for networks with unit capacities. The table however is definitely missing the algorithm with running time O(m n^(1/2) polylog(n) log^2 U) by Lee and Sidford: https://arxiv.org/abs/1312.6713 (FOCS 2014). I'm not adding it myself right now because I do not know which method for writing polylog(n) in the running time is preferred by WP. In research papers we often use tilde-O notation, but it does not seem appropriate here. — Preceding unsigned comment added by 2001:628:2120:630:F1B4:3809:85FE:5DE (talk) 12:42, 11 January 2018 (UTC)

External links modified (January 2018)

Hello fellow Wikipedians,

I have just modified one external link on Maximum flow problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf to http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:08, 23 January 2018 (UTC)

Subsection "Minimum path cover in directed acyclic graph"

There are numerous issues with the subsection "Minimum path cover in directed acyclic graph" (besides no cited sources):

1. The terms "in-degree" and "out-degree" are not defined in this article, but if we assume they take the usual meaning – "positive out-degree" of $v$ means that there is one or more edges leaving $v$ – then $V_{in}$ and $V_{out}$ can be non-disjoint, which contradicts the statement that $G'$ is a bipartite graph. Although it can be understood that $V_{in}$ and $V_{out}$ contain "symbolic" vertices constituting the original vertices of $V$, such that the symbolic vertices for a certain $v\in V$ are distinct in $V_{in}$ and $V_{out}$, it is necessary to make this distinctness explicit, for example using a notation such as $\{v_{\textrm {in}}\vert v\in V\land v{\text{ has positive in-degree}}\}$.
2. Similarly, taking the current definition of $V_{in}$ and $V_{out}$, $E'$ simply equals $E$, since for each $(u,v)\in E$ it certainly holds that out-degree of $u$ and in-degree of $v$ are both positive. This again contradicts the statement that $G'$ is a bipartite graph, since $V_{out}$ and $V_{in}$ are in general not independent.
3. Kőnig's theorem relates vertex covers to matchings in bipartite graphs. It is not clear how one would use Kőnig's theorem to relate matchings in $G'$ to verex-disjoint path covers in $G$.
4. Overall, it is not clear whether and why are the observations in this section correct. As currently stated, it leaves too much room for interpretation and gives no intuitive explanation of the principle, althought the intuition is quite simple.

I would suggest either incorporating these remarks or removing the subsection. --84.245.120.59 (talk) 19:44, 21 November 2020 (UTC)