LP, IP, Relaxations & LP Rounding

CS F364 — Design & Analysis of Algorithms | Summer 2026

LP formulation, integer programming, LP relaxation, LP rounding, Vertex Cover, integrality gap.

← Practice

NoteProblem G1

Convert the following integer program to an LP relaxation and solve it (graphically or by inspection):

\begin{aligned} \max \quad & 3x + 2y \\ \text{s.t.} \quad & x + y \le 2 \\ & 2x + y \le 3 \\ & x, y \in \{0,1\} \end{aligned}

What does the optimal LP value tell you about the IP optimal?

LP relaxation: 0 \le x, y \le 1 (same constraints otherwise). Feasible set = polygon with vertices (0,0), (1,0), (1,1), (0,1). Evaluate 3x+2y: - (0,0)=0, (1,0)=3, (1,1)=5, (0,1)=2.

LP optimum = 5 at (1,1). IP optimum = 5 (same point). Since x,y are already integer, the LP upper bound is tight — no integrality gap.

NoteProblem G2

For Vertex Cover on a path graph with 4 vertices (edges: (1,2),(2,3),(3,4)):

  1. Write the IP formulation.
  2. Write the LP relaxation.
  3. Solve the LP (you should get x_1=x_4=0.5, x_2=x_3=0.5 or equivalent).
  4. Apply rounding: set x_v = 1 if x_v \ge 1/2. What vertex cover do you get? Is it optimal? What is the approximation ratio on this instance?
  1. IP: \min x_1+x_2+x_3+x_4 s.t. x_1+x_2 \ge 1, x_2+x_3 \ge 1, x_3+x_4 \ge 1, x_i \in \{0,1\}.
  2. LP: same but 0 \le x_i \le 1.
  3. LP opt = 2 (e.g., x_1=x_4=0.5, x_2=x_3=0.5 gives sum = 0.5+0.5+0.5+0.5 = 2).
  4. Rounding: x_1=x_4=0.5 \to 1, x_2=x_3=0.5 \to 1. Cover = \{1,2,3,4\} size 4. This is not optimal (optimal VC = \{2,3\} size 2). Approximation ratio on this instance: 4/2 = 2.
NoteProblem G3

Integrality gap: For Vertex Cover, consider a triangle graph (3 vertices, 3 edges). Write the LP relaxation and find its optimal fractional value. Compare with the optimal integer value. What is the integrality gap (ratio of IP optimal to LP optimal)? How does this relate to the 2-approximation guarantee?

Triangle: vertices 1,2,3, edges (1,2),(2,3),(1,3). IP: \min x_1+x_2+x_3 s.t. x_1+x_2 \ge 1, x_2+x_3 \ge 1, x_1+x_3 \ge 1, x_i \in \{0,1\}. IP opt = 2 (any two vertices). LP: same with 0 \le x_i \le 1. LP opt = 1.5 (all x_i=0.5 gives 0.5+0.5+0.5=1.5 and all constraints satisfied). Integrality gap = 2 / 1.5 = 4/3. The 2-approximation guarantee comes from the fact that the integrality gap can be as bad as 2 on some graphs (e.g., odd cycles).