# Python辅导 | CSOR W4246 Theoretical part

CSOR W4246 – Fall, 2019

HW3 – Theoretical part (100 points)

Out: Saturday, October 26, 2019

Due: 11:59pm, Saturday, November 9, 2019

Please keep your answers clear and concise. For all algorithms you suggest, you must prove correctness and

give the best upper bound that you can for the running time. You should always describe your algorithm

clearly in English and give pseudocode. If you give a reduction or a linear program, you should follow the

steps discussed in class.

You must submit your assignment as a pdf file. Other file formats will not be graded, and will automatically

receive a score of 0. I recommend you type your solutions using LaTeX. For every theoretical assignment,

you will earn 5 extra credit points if you type your solutions. If you do not type your solutions, make sure

that your hand-writing is very neat, your scan is high-quality and your name and UNI are clearly written

on your homework.

You should not use any external resources for this homework. You should write up the solutions

entirely on your own. Collaboration is limited to discussion of ideas only (see also the course syllabus).

Similarity between your solutions and solutions of your classmates, or solutions posted online, will result in

receiving a 0 in this assignment and possibly further disciplinary actions.

1. (25 points) A flow network with demands is a directed capacitated graph with potentially

multiple sources and sinks, which may have incoming and outgoing edges respectively. In

particular, each node v ∈ V has an integer demand d(v); if d(v) > 0, v is a sink, while if

d(v) < 0, it is a source. Let S be the set of source nodes and T the set of sink nodes.

A circulation with demands is a function f : E → R+ that satisfies

(a) capacity constraints: for each e ∈ E, 0 ≤ f(e) ≤ c(e).

(b) demand constraints: For each v ∈ V , f

in(v) − f

out(v) = d(v).

We are now concerned with a decision problem rather than a maximization one: is there a

circulation f with demands that meets both capacity and demand conditions?

i. Derive a necessary condition for a feasible circulation with demands to exist.

ii. Reduce the problem of finding a feasible circulation with demands to Max Flow.

2. (25 points) In many applications, on top of the node demands introduced in the previous

problem, the flow must also make use of certain edges. To capture such constraints, consider

the following variant of the previous problem.

You are given a flow network G = (V, E) with demands where every edge e has an integer

capacity ce, and an integer lower bound `e ≥ 0. A circulation f must now satisfy `e ≤ f(e) ≤ ce

for every e ∈ E, as well as the demand constraints. Determine whether a feasible circulation

exists.

3. (25 points) Similarly to a flow network with demands, we can define a flow network with

supplies where each node v ∈ V now has an integer supply sv so that if sv > 0, v is a source

and if sv < 0, it is a sink, and the supply constraint for every v ∈ V is f

out(v) − f

in(v) = sv.

In a min-cost flow problem, the input is a flow network with supplies where each edge (i, j) ∈ E

also has a cost aij . Given a flow network with supplies and costs, the goal is to find a feasible

flow f : E → R+ —that is, a flow satisfying edge capacity constraints and node supplies—

that minimizes the total cost of the flow.

(a) Show that max flow can be formulated as a min-cost flow problem.

(b) Formulate a linear program for the min-cost flow problem.

4. (i) (20 points) You are given a data set of m red and n white points on the plane. You want

to separate the red from the white points by a line, if possible; that is, you are looking for a

line such that all the red points are on one side, all the white points on the other side and no

points lie on the line. Form a linear program to solve this problem.

(ii) (5 points) Now suppose that your linear program above is infeasible, so no line can

separate the red from the white points. You are now wondering whether a quadratic function

(parabola) of the form ax2 +bx+c could separate the points. Can you form a linear program

for this problem? Justify your answer.

RECOMMENDED exercises: do NOT return, they will not be graded.

1. Run the Ford-Fulkerson algorithm on the following network, with edge capacities as shown,

to compute the max s-t flow. At every step, draw the residual graph and the augmenting

paths. Report the maximum flow along with a minimum cut.

d

a

s t

10

1

5

10

b c

3 6

3 3

1 2

5

2. There are many variations on the maximum flow problem. For the following two natural

generalizations, show how to solve the more general problem by reducing it to the original

max-flow problem (thereby showing that these problems also admit efficient solutions).

• There are multiple sources and multiple sinks, and we wish to maximize the flow between

all sources and sinks.

• Both the edges and the vertices (except for s and t) have capacities. The flow into and

out of a vertex cannot exceed the capacity of the vertex.