Homework 1: max flow/min cut basic algorithms (Due 11/11) Last Name First Name 1. Given the capacitated graph

Homework 1: max flow/min cut basic algorithms (Due 11/11)

Last Name First Name

1. Given the capacitated graph G = (N, A) of Figure 1:

1. Evaluate the maximum (s, t) flow, f

(s) 2. List the collection of f

(s) (s, t) paths

3. Find the minimum (s, t) cut and at least two cuts satisfying f

(s) < u(δ(R))

5 5

5

10 7 9

2

3

2

13

3

4

s t

Figure 1

2. Given the graph G = (N, A) of Figure 2, identify the minimum (s, t) cut.

s t

10

10 100

100

100

Figure 2

3. A company has three departments D1, D2, D3 and the daily work is organized in two work shifts S1 and S2. The company requires to meet the following constraints:

1. the staffing level for each department and for each shift must be in given range, as reported in Table 1 (minimum number of workers, maximum number of workers)

1

Homework 1: max flow/min cut basic algorithms (Due 11/11)

Last Name First Name

D1 D2 D3

S1 [5, 10] [8, 14] [7, 10]

S2 [6, 9] [7, 13] [8, 12]

2. the company must allocate over all shifts at least 13 workers in department D1, 20 workers in department D2 and 18 workers in department D3.

3. the company must allocate over all departments at least 25 workers in shift S1 and 24 workers in shift S2.

Discuss a max-flow model that can help in finding the minimum number of workers required to satisfy all constraints.

4. Given the matrix in Figure 3, round each entry in the matrix such that the sum of the rounded elements in each row equals the rounded row sum and the sum of the rounded elements in each column equals the rounded column sum.

3.5 2.6 8.7 4.2 19.1 4.3 5.1 5.2 6.8 21.4 10.2 5.4 7.3 8.9 31.8 18.1 13.1 21.2 19.9

2