Description
1. In the network below (See Fig. 1), the demand values are shown on
vertices (supply values are negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge.
Determine if
there is a feasible circulation in this graph. Please complete the following
steps.
Figure 1
(a) Remove the lower bounds on each edge. Write down the new demands
on each vertex A, B, C, D, E, in this order.
(b) Solve the circulation problem without lower bounds. Write down the
max-flow value.
(c) Is there is a feasible circulation in the original graph? Explain your
answer.
2. The organizers of the 2022 US Open Tennis Championships are working
on making the draws for the first round and scheduling the matches.
They are faced with several constraints in doing so.
There are 2N players, seeded (ranked) from 1 to 2N. The players are
divided into two halves – the top half containing players seeded 1 to N,
and the bottom half containing seeds N + 1 to 2N. The first round
consists of N matches among the 2N players, each being one where a
top-half player plays a bottom-half player.
Additionally, to keep them a bit more competitive, each match must be
between players whose seeds differ by at most N0
(a given constant > N).
The sports facility has courts C1, …, Cm. The matches will be scheduled
in timeslots T1, …, Tk. Matches can run in parallel on different courts in a
given timeslot. Assume all courts are available in all timeslots, however a
single court can have at most p matches to preserve surface quality. For
broadcasting reasons, in any given timeslot, there should be at least one
match being played and at most r of them.
The bottom-half players were given the option to make requests if they
preferred to play in certain timeslots, and each of them has specified k
0
of the k timeslots that they are okay to play in. Seeded players on the
other hand were given the option to make requests to avoid playing on
certain courts, and each of them has specified m0 of the m courts that
they do not want to play on.
Describe a Network Flow/Circulation based algorithm to determine if it
is possible to come up with a feasible schedule of matches based on the
above constraints.
3. A company is currently trying to fill a large order of steel, brass, and
pewter, measured in tons. Manufacturing each ton of material requires a
certain amount of time, and a certain amount of special substance (SS),
both of which are limited and are given in below table. Note that it
is acceptable to manufacture a fraction of a ton (e.g. 0.5t) of material.
Specifically, the company currently has 8 hours of time, and 20 units
of special substance (SS). Manufacturing each ton of the three products
requires:
Figure 2: Table describing the amount of time taken and special substance (SS) required for each product.
(a) Write down a linear program that determines the maximum amount
of products (in tons) that the company can make.
(b) Due to the potential danger posed by the special substance (SS),
the company would like to use up as much of its supply of special
substance (SS) as possible, while:
i. spending at most 8 hours
ii. manufacturing a total of at least 2 tons of steel plus pewter.
4. Suppose that a cement supplier has two warehouses, one located in city A
and another in city B. The supplier receives orders from two customers,
one in city C and another in city D.
The customer in city C needs at
least 50 tons of cement, and the customer in city D needs at least 60 tons
of cement.
The amount of cement at the warehouse in city A is 70 tons,
and the number of units at the warehouse in city B is 80 tons. The cost
of shipping each ton of cement from A to C is 1, from A to D is 2, from
B to C is 3, and from B to D is 4.
Formulate the problem of deciding how many tons of cement from each
warehouse should be shipped to each customer to minimize the total
shipping cost as a linear programming. You can assume that the values
of units to be shipped are real numbers.
5. Write down the dual program of the following linear program. There is
no need to provide intermediate steps.
max(x1 − 3×2 + 4×3 − x4)
subject to
x1 − x2 − 3×3 ≤ −1
x2 + 3×3 ≤ 5
x3 ≤ 1
x1, x2, x3, x4 ≥ 0
6. Given an undirected graph G = (V, E), a vertex cover is a subset of V
so that every edge in E has at least one endpoint in the vertex cover.
The problem of finding a minimum vertex cover is to find a vertex cover
of the smallest possible size. Formulate this problem as an integer linear
programming problem.
7. Assume that you are given a polynomial time algorithm that given a 3-
SAT instance decides in polynomial time if it has a satisfying assignment.
Describe a polynomial time algorithm that finds a satisfying assignment
(if it exists) to a given 3-SAT instance.
8. The graph five-coloring problem is stated as follows: Determine if the
vertices of G can be colored using 5 colors such that no two adjacent
vertices share the same color. Prove that the five-coloring problem is
NP-complete.
Hint: You can assume that graph 3-coloring is NP-complete
9. Longest Path is the problem of deciding whether a graph G = (V, E)
has a simple path of length greater or equal to a given number k. Prove
that the Longest path Problem is NP-complete by reduction from the
Hamiltonian Path problem.
10. There are a set of courses in USC, each of them requiring a set of disjoint
time intervals. For example, a course could require the time from 9am
to 11am and 2pm to 3pm and 4pm to 5pm.
You want to know, given a
number K, if it’s possible to take at least K courses. Since you want to
study hard and take courses carefully, you can only take one course at any
single point in time (i.e. any two courses you choose can’t overlap).
Show
that the problem is NP-complete, which means that choosing courses is
indeed a difficult thing in our life. Use a reduction from the Independent
set problem.
