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.