Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently studying network flow algorithms and one of its application is supposed to be "Project Selection". A (more) complete description is given here, but the problem basically is this:

There is a graph $G$ with a number of projects $P$ as nodes. Projects have a revenue $p_i$ and a dependency from project $j$ on $i$ is given as an edge $(j,i)$.

Now it is said that the minimum cut will provide the most efficient set of projects to take if makes a source node $s$, sink node $t$ and make an edge $(s,i)$ if $p_i > 0$ and an edge $(i,t)$ if $p_i < 0$

There are however several cases I can think of that seem impossible to solve in this matter.

Consider for example a case with only 1 project ($P = {a}$) with a revenue of +10. Clearly the most profitable set of projects to do is ${a}$, but a flow is impossible in this case (and thus all possible cuts are minimal, including those without $a$).

No unprofitable projects

Or if there is a project with no cost, it will not have a connection with the source nor sink and as such does not have to be in the minimum cut. (pic coming later)

(other counter-examples I can think of basically are all based on these 2 problems)

Can anyone shed some light on this algorithm for me?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You misunderstood the result. Whether a flow is possible or not is not relevant. In your first case, where the graph is

$ s \to a \, \ t $

the minimal cut (=partition of the nodes into two sets, one containing s and the other t) is ({s,a}, {t}) which has capacity 0 because there are no edges from one set to the other. The other cut ({s},{a,t}) has capacity 10 (the capacity of the edge from s to a). In the other example with revenue 0, both possible cuts have capacity 0 so you can either do project a or not; both are optimal.

share|improve this answer

I hesitate to write this up as an answer, but I guess I don't have the 'comment' privilege yet.

These types of issues are important to understand, as they force you to understand the problem in more depth and come up with a model that accurately describes it without too much fluff.

Anytime you encounter a case that breaks your model, you can try to add something to the model that allows you to model it accurately.

The one project case is obvious: there's no problem to solve. You either do the project or you don't.

A project with zero cost almost makes no sense. If the cost is zero, then I'd try to change the model to more accurately describe the problem. In the simplest case, a business choosing projects to tackle would have at least two costs in mind: time spent, money spent.

Now, suppose project X1.0 (v1.0) is already complete, but it sucks. The choice is one of:

  1. X1.0 -> Y1.0 (Just use it and put up with the headaches)
  2. X1.1 -> Y1.0 (Improve X1.0)
  3. X2.0 -> Y1.0 (Re-write it)

The cost of traversing the edge from X to Y in (1) is zero. However, a proper model for this would have 3 nodes in the graph for Y: one for each path. Treating Y as a single node with separate edges then creates the implicit assumption that the path from Y1.0 to Z1.0 is the same no matter which of the 3 options you pick.

In short: this is what mathematical modeling is all about. Analyzing the problem and coming up with a good way to accurately model it. If something breaks it, more than likely it's your model.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.