Exercise 02 notes - Lösungen zur Übungsaufgabe 2 PDF

Preview

Summary

Lösungen zur Übungsaufgabe 2...

Description

Discrete Optimization Tutorial Filip Krumpe

WS 2016/17 https://www.fmi.uni-stuttgart.de/alg/lehre/ ws16/discrete-optimization-ws-1617

Institut f¨ ur Formale Methoden der Informatik Abt. Algorithmik Universit¨ at Stuttgart

Exercise Sheet 2

Problem 1 (a) Consider the following two procedures to compute GfD in the capacity scaling algorithm: 1. Remove edges from G with capacity < D. Compute the residual network GD f of the resulting subgraph. 2. Compute the residual network of G. Remove edges with capacity < D from the computed residual network. Prove or disprove: Both procedures are equivalent and result in the same GD f . (b) Why do we need to use procedure 2 to compute the residual network when using capacity scaling? If we use procedure 1, how does the running time of the capacity scaling algorithm change?

Notes: The following nodes do not claim to be a complete solution!

@(a): There are counterexamples showing that both procedures are producing different output. The solution of the first precedure can countain edges with capacity < D. @(b): When using procedure 1 the residual networks in the inner loop of the capacity scaling algorithm might contain edges with capacity < D. The running time analysis does not apply in this scenario. Using procedure 1 might result in a running time that is equal to the RT of the original FF (i.e. potentially exponential in the input size!).

1

Problem 2 (a) In order to compute a MinCostFlow we initially need to find a feasible flow f for a given MinCostFlow instance. Show how this can be done using Ford Fulkerson’s algorithm. Hint: Pay attention to the varying input for Ford Fulkerson’s algorithm and the cycle cancelling algorithm. (b) Use your solution to compute an initial maximum flow for the MinCostFlow instance in Problem 3.

Notes: The following nodes do not claim to be a complete solution!

@(a): Notice: MinCostFlow input is a graph as well as a capacity and a cost function on the edges and a supply function on the vertices. MaxFlow input is a graph, a capacity function and two distinct nodes s and t! Construct a MaxFlow instance from the MinCostFlow instance: Introduce two new nodes: s and t. Connect s to every node having a positive supply value in the MinCostFlow instance. Assign a capacity equals to the supply value of the target node. Connect each node with negative supply value to t and assign a capacity of the negated supply value. Adopt the edges and capacities of the MinCostFlow instance. Solve the created MaxFlow instance. Use the resulting flow as initial flow of the MinCostFlow instance. @(b): Your turn!

2

Problem 3 Compute the MinCostFlow for the following instance using the cycle cancelling algorithm. Here capacity and costs are denoted by capacity/cost: [+1]

b 3/3

4/2

[-2]

[+4]

a

8/10 2/2

d 5/1

c [-3]

Start with the following feasible maximum flow: f ((a, b)) = 3, f ((a, c)) = 1, f ((b, c)) = 2, f ((b, d)) = 2, f ((c, d)) = 0. In the first iteration use acdba to reroute the flow.

Notes: The following nodes do not claim to be a complete solution!

Your turn! You will need two iterations to reach the result you found in the lecture.

Problem 4 In class you assumed that

P

v ∈V :b(v )>0

b(v) 6= −

P

b(v) in a valid MinCostFlow instance.

v ∈V :b(v )0

P

b(v)

and b(t) =

v∈V :b(v)...