Talk:Maximum flow problem

Missing equations/images

edit

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

Solution

edit

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)Reply

Diagram 4.4.1 Max flow with vertex capacities ==

edit

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 (talkcontribs) 00:50, 7 November 2011 (UTC)Reply

Real world example

edit

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)Reply

What does "integral capacity" mean?

edit

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

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

History

edit

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)Reply

Minimum path cover in directed acyclic graph

edit

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 (talkcontribs) 19:30, 5 December 2012 (UTC)Reply

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)Reply

Carpool example

edit

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)

edit

The problem exactly is that   people are pooling a car for   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   people use the car on a day, each person has a responsibility of  . Thus, for every person  , his driving obligation   as shown. Then person   is required to drive only   times in   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   exists then such a fair setting exists and such a flow of value   always exists.

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

Update Table with known results

edit

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)Reply

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)Reply

edit

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:

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)Reply

Subsection "Minimum path cover in directed acyclic graph"

edit

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   means that there is one or more edges leaving   – then   and   can be non-disjoint, which contradicts the statement that   is a bipartite graph. Although it can be understood that   and   contain "symbolic" vertices constituting the original vertices of  , such that the symbolic vertices for a certain   are distinct in   and  , it is necessary to make this distinctness explicit, for example using a notation such as  .
  2. Similarly, taking the current definition of   and  ,   simply equals  , since for each   it certainly holds that out-degree of   and in-degree of   are both positive. This again contradicts the statement that   is a bipartite graph, since   and   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   to verex-disjoint path covers in  .
  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)Reply