Information Technology > Study Notes > CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.0 (All)

CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.0

Document Content and Description Below

CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.01. Prove infeasibility. (25 pts.) You are trying to solve a circulation problem, but it is not feasible. The problem has demands, but ... no capacity limits on the edges. More formally, there is a graph G = (V, E), and demands dv for each node v (satisfying ∑v∈V dv = 0), and the problem is to decide if there is a flow f such that f(e) ≥ 0 and fin(v) − fout(v) = dv for all nodes v ∈ V . Note that this problem can be solved via the circulation algorithm from Section 7.7 by setting ce = +∞ for all edges e ∈ E. (Alternately, it is enough to set ce to be an extremely large number for each edge – say, larger than the total of all positive demands dv in the graph.) You want to fix up the graph to make the problem feasible, so it would be very useful to know why the problem is not feasible as it stands now. On a closer look, you see that there is a subset U of nodes such that there is no edge into U, and yet ∑v∈U dv > 0. You quickly realize that the existence of such a set immediately implies that the flow cannot exist: The set U has a positive total demand, and so needs incoming flow, and yet U has no edges into it. In trying to evaluate how far the problem is from being solvable, you wonder how big the demand of a set with no incoming edges can be. Give a polynomial-time algorithm to find a subset S ⊂ V of nodes such that there is no edge into S and for which ∑v∈S dv is as large as possible subject to this condition [Show More]

Last updated: 3 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: