- This assignment has 50 available points (there is also one free point for Question 0). Full marks
will be obtained for 45 points.
The following question is worth 1 point:
Question 0. How many hours did you (as an individual) spend working on this assignment? Answer
= .
[15] 1. Taking Duals.
5 Give the dual for the following LP.
max 2x1 + 3x2 + x3 − 8x4 + 2x5
x1 + x2 − x4 + x5 ≤ 10
x1 + 2x2 + x3 + 4x4 − x5 = 5
x1, x2, x3 ≥ 0
Note. There is no need to simplify your answer in any way.
5 State the Complementary Slackness Conditions for the primal and dual LPs in Part (a).
5 Let G = (V, E) be a directed graph with positive integer edge weights ce for each e ∈ E.
We are also given s, t ∈ V and define P to be the set of all (simple) st-paths. (Yes, there
may be exponentially many. Dont worry about that.)
Consider the following LP:
maxP
P ∈P
P
xP
P ∈P:e∈P
xP ≤ ce for each e ∈ E
xP ≥ 0 for each P ∈ P
Give the dual LP for this problem. At least 1 mark will already be given if you clearly
and correctly describe the dual variables. Then for full marks explain the dual objective
and dual constraints.
Give a combinatorial interpretation for any optimal solution to the dual LP.
[10] 2. Skew-symmetric Games
The payoff matrix (aij ) for a two-person zero-sum game is said to be skew symmetric if the matrix
has the same number of rows and columns and aij = −aji for each choice of i and j. Note that
in this game, if Player 1 plays strategy i and Player 2 plays strategy j, then the payoff is aij to
Player 2 and −aij to Player 1.
5 Show that if Players 1 (row) and 2 (column) use the same mixed strategy, x1 = y1, x2 =
y2, …, xn = yn, then the expected payoff to Player 2 is
X
i
X
j
xiaijyj
and this equals zero.
1
5 Consider any mixed strategy x1, x2, …, xn for Player 2. If the player is conservative, she
will expect that her payoff w would be no better than the worst responding strategy from
Player 1. This implies that w must satisfy the following inequalities.
a11x1 + a12x2 + . . . + a1nxn ≥ w
a21x1 + a22x2 + . . . + a2nxn ≥ w
.
.
.
an1x1 + an2x2 + . . . + annxn ≥ w
Consider multiplying these constraints by y1 = x1, y2 = x2, …yn = xn, respectively, and
add. Use this manipulation, together with part (a), to conclude that the best possible
expected payoff for Player 2 for any mixed strategy is ≤ 0. Similarly argue that the best
possible payoff to Player 1 is ≤ 0. Conclude from linear-programming strong duality
that there exists mixed strategies where the payoff to each player is 0.
[10] 3. Difference-Constrained Linear Programs. We consider a special class of linear programs.
Let x1, . . . , xn ∈ R be n variables. We have m constraints, each of which has one of the following
two forms:
• xik − xjk ≤ αk,
• xik − xjk ≥ αk.
where ik, jk ∈ [n] and αk ∈ Z for k ∈ [m].
8 Give an O(mn) algorithm to decide whether there is a feasible non-negative solution
(a1, . . . , an) that satisfies all of the constraints, and if so, find such a solution.
Hint. This is not a Simplex Algorithm question. Rather it connects ideas between the
first half of the course and the topic of linear programming.
2 Explain how to extend your algorithm for the first part to handle constraints of the form:
• xik − xjk < αk, • xik − xjk > αk.
[15] 4. A 3
2
-Approximation for Vertex Covers on 4-Colorable Graphs.
Let G = (V, E) be a undirected graph. A vertex cover is a set U ⊆ V that includes at least one
endpoint of each edge. The minimum vertex cover problem, denoted by MinVertexCover, asks
for the smallest number k such that G has a vertex cover of size k.
Suppose that G is 4-colorable. Recall that this means that there exists c : G → {0, 1, 2, 3}, called
a 4-coloring of G, such that c(u) ̸= c(v) for all uv ∈ E.
5 Give an LP relaxation of MinVertexCover with variables xv ∈ [0, 1] for v ∈ V .
In other words, this would be an LP of the form min P
v
xv : Ax ≥ b, 0 ≤ x ≤ 1 with the
following property. For any vertex cover S of G, the incidence vector 1S
is feasible for
your LP.
Recall. The incidence vector of a set S, denoted by 1
S
, is defined by 1
S
v = 1 if v ∈ S,
otherwise 1
S
v = 0.
5 Show that your LP has an optimal solution such that xv ∈ {0,
1
2
, 1} for each v ∈ V .
Note. Even if you are unable to prove this, you may use this result to complete the last
part of the question.
2
5 Let c : G → {0, 1, 2, 3} be a 4-coloring of G. Without loss of generality we can assume
|V
1/2
0
| ≤ |V
1/2
1
| ≤ |V
1/2
2
| ≤ |V
1/2
3
|
where V
1/2
i = {v ∈ V : xv = 1/2, c(v) = i} for i = 0, 1, 2, 3.
Let
S = {v ∈ V : xv = 1} ∪
v ∈ V : xv =
1
2
, c(v) ̸= 3
.
Show that S gives a 3
2
-approximation for MinVertexCover.
No More Worries!
Our orders are delivered strictly on time without delay
Paper Formatting
- Double or single-spaced
- 1-inch margin
- 12 Font Arial or Times New Roman
- 300 words per page
No Lateness!
Our orders are delivered strictly on time without delay
Our Guarantees
- Free Unlimited revisions
- Guaranteed Privacy
- Money Return guarantee
- Plagiarism Free Writing
Advanced Algorithm Design and Analysis
Satisfaction Guaranteed
- Research Paper Writing
- Essay Writing
- Dissertation Writing
- Thesis Writing
Why Choose Us
- Money Return guarantee
- Guaranteed Privacy
- Written by Professionals
- Paper Written from Scratch
- Timely Deliveries
- Free Amendments