PadhaikoAll subjects

Approximation and Optimization Algorithms

Advanced Algorithms (ENCT 467)

Open in the Padhaiko app

6.1 Approximation algorithms

When an optimization problem is NP-hard, no polynomial-time algorithm is known to find an exact optimal solution on all instances (unless ). Approximation algorithms run in guaranteed polynomial time and return a feasible solution whose cost is provably close to .

Definition

Approximation Ratio, PTAS, and FPTAS

An algorithm has an approximation ratio if for every input of size , the cost of the returned solution and the optimal cost satisfy:

Special classes of near-optimal approximation algorithms:

Example: Metric Traveling Salesperson Problem (TSP)


6.2 Vertex cover approximation

Given an undirected graph , a vertex cover is a subset such that every edge has at least one endpoint in ( or ). Finding a minimum-cardinality vertex cover is NP-hard.

The -Approximation Matching Algorithm

2-Approximation Vertex Cover AlgorithmText
APPROX-VERTEX-COVER(G):
  C = empty set
  E' = E(G)
  while E' is not empty:
      pick any edge (u, v) in E'
      add BOTH u and v to C
      remove from E' every edge incident to u or v
  return C
Theorem

2-Approximation Guarantee for Vertex Cover

APPROX-VERTEX-COVER(G) runs in time and returns a valid vertex cover satisfying:

where is a minimum vertex cover of .

Example 1

1

Consider a -vertex graph with edges .

  1. Trace APPROX-VERTEX-COVER(G) by picking edges in the order listed (skipping already covered edges).
  2. Find the true optimal vertex cover size and verify that the approximation ratio .

Trace APPROX-VERTEX-COVER(G):

  • Pick edge : add and to . Remove edges incident to or : . Remaining .
  • Pick edge : add and to . Remove edges incident to or : . Remaining .
  • Pick edge : add and to . Remove . is now empty.
  • Returned cover: , size (from matching of size ).

Find optimal vertex cover and verify the ratio: Every edge is covered by (check: and via ; via ; via ). Because matching has vertex-disjoint edges, , so .

  • Ratio: .
Answer:

APPROX-VERTEX-COVER picks matching and outputs (), while the optimal cover has size , giving ratio .


6.3 Set cover approximation

Definition

Set Cover Problem

Given a finite universe of elements and a family of subsets of with (optionally with weights ), Set Cover seeks a minimum-size (or minimum-weight) subfamily whose union covers all of .

Greedy -Approximation Algorithm

At each iteration, let be the set of remaining uncovered elements (initially ). The Greedy Set Cover algorithm repeatedly selects the subset that maximizes (or minimizes cost per newly covered element in the weighted version), adds to , and updates until .

Theorem

Logarithmic Approximation Ratio of Greedy Set Cover

Greedy Set Cover runs in polynomial time and achieves an approximation ratio of:

where and is the -th harmonic number. (Unless , no polynomial-time algorithm can approximate Set Cover within .)

Charging Argument Intuition: Whenever greedy picks covering newly covered elements at cost , charge cost to each of those elements. Consider any optimal set of size : as elements of get covered, when elements of remain uncovered, itself could cover elements at cost , so greedy's chosen set must cover at least elements (charge ). Summing charges over all elements of yields at most .

Example 2

2

Let universe () and subsets:

Trace Greedy Set Cover (breaking ties by lowest index), compare with the optimal cover , and verify the upper bound ().

Trace Greedy Set Cover:

  • Initially . Coverage sizes: , , , , . Greedy picks ( elements), leaving .
  • Next round: , , , . Breaking ties by lowest index, Greedy picks (covering ), leaving .
  • Final round: , . Breaking ties by lowest index, Greedy picks (covering ), leaving .

Thus Greedy outputs of size .

Compare with optimal cover and bound: Notice already covers using only sets, so . The achieved ratio is:

Answer:

Greedy Set Cover outputs ( sets), whereas the optimal cover is ( sets), giving approximation ratio .


6.4 Linear programming concepts

Linear Programming (LP) optimizes a linear objective function over a feasible region defined by linear equality and inequality constraints. Unlike integer programming, general LP is solvable in polynomial time.

Definition

Standard Form and Slack Form of an LP

In standard form, an LP with decision variables and constraints is:

Introducing nonnegative slack variables converts each inequality into an equality constraint (slack form), enabling algebraic pivoting in the Simplex algorithm.

Geometry, Duality, and Solvers


6.5 Integer programming applications

Restricting LP decision variables to integers ( or ) produces an Integer Linear Program (ILP), which is NP-hard in general yet extraordinarily expressive for combinatorial optimization.

LP Relaxation and Rounding Technique

  1. Formulate Exact ILP: Express the discrete problem with indicator variables (e.g., for vertex cover).
  2. LP Relaxation: Drop the integrality constraint to , solving the relaxed LP in polynomial time to obtain fractional optimum with (for minimization).
  3. Rounding: Convert fractional back to a feasible integer solution while bounding the cost blow-up:
    • Weighted Vertex Cover (-Approximation):

Since , at least one of must be ! Rounding guarantees every edge is covered and total weight:

Example 3

3

Consider a triangle graph on vertices with vertex weights , , and .

  1. Write the ILP and its LP relaxation for Minimum Weighted Vertex Cover on .
  2. Compare the optimal LP relaxation solution, the deterministic rounding solution (), and the true optimal integer vertex cover.

Formulate ILP and LP Relaxation:

subject to edge constraints , , , and (ILP) or (LP relaxation).

Solve LP relaxation and apply -rounding: Setting satisfies all three edge constraints () with objective:

(Dual check: assigning satisfies , , , with dual objective , certifying LP optimality by Strong Duality!) Deterministic rounding has weight .

Compare with optimal integer cover: To cover all three edges of , at least two vertices must be chosen; the cheapest pair is with weight . Notice and .

Answer:

The LP relaxation achieves at , deterministic rounding gives of weight , and the true optimal ILP solution is of weight (ratio ).


Exercises

Practice Exercises — Approximation and Optimization Algorithms

Question 1

Define the approximation ratio and distinguish between a PTAS and an FPTAS. For a -city metric TSP with symmetric distances , compute the MST weight, an upper bound from the double-tree tour, and the exact optimal tour cost.

Definitions: An algorithm is a -approximation if for all inputs of size . A PTAS runs in polynomial time in for fixed (e.g., ), whereas an FPTAS runs in time polynomial in both and (e.g., ).

Metric TSP MST and tour:

  • MST: Pick the three smallest edges , , and (no cycles), giving .
  • Double-tree -approx bound: Tour cost . (Specifically, preorder traversal uses .)
  • Optimal tour: costs (any tour using diagonals costs at least ).
Answer:

PTAS is polynomial in for fixed , while FPTAS is polynomial in both and . Here MST weight is , the double-tree guarantee is , and the actual tour has optimal cost .

Question 2

Prove that APPROX-VERTEX-COVER achieves a -approximation ratio. Construct a -vertex graph where picking a valid -edge matching produces a cover of size while the optimal vertex cover has size , achieving the tight ratio .

Proof of -approximation: The picked edges form a matching (no two share an endpoint) because all edges incident to both endpoints are deleted at each step. Any optimal vertex cover must include at least one endpoint from each edge in , so . Since the algorithm adds both endpoints of every edge in , .

Tight -vertex example ( or path ): Take the -cycle with edges .

  • If APPROX-VERTEX-COVER picks and , it outputs of size .
  • The optimal vertex cover is (or ) of size .
  • Ratio: .
Answer:

Because the chosen edges form a vertex-disjoint matching , . On the -cycle , picking and produces against , achieving the tight ratio .

Question 3

Explain why Greedy Set Cover guarantees an -approximation and state its hardness-of-approximation threshold. For universe with subsets , , , , and , trace Greedy Set Cover and compare its cover size with the optimal cover.

Approximation ratio and hardness: Using a charging argument over the elements of each optimal set , each element covered when elements of remain pays at most , summing to at most . Feige proved that Set Cover cannot be approximated within in polynomial time unless (and ).

Trace Greedy Set Cover vs. Optimal:

  • Iteration 1: covers elements (most among ), leaving .
  • Iteration 2: covers , covers , covers , covers . Picking (or ) covers , leaving .
  • Iteration 3: Pick (or ) to cover .

Greedy outputs sets (e.g., or ), whereas the optimal cover is of size (ratio ).

Answer:

Greedy Set Cover achieves an ratio (essentially best possible modulo constants). On the given instance, Greedy picks sets vs. optimal ( sets), giving ratio .

Question 4

State the Weak Duality and Strong Duality theorems of Linear Programming. Given the primal LP:

write its dual LP, solve both, and verify Strong Duality at the optimal point.

Weak and Strong Duality: Weak Duality states that for any primal feasible and dual feasible , . Strong Duality states that if the primal (or dual) has a finite optimal solution , the other also has an optimal solution with .

Dual LP and optimal solution: With dual variables for the three constraints:

  • Primal optimum: Since has higher objective weight (), push (max allowed by ) and (using ), giving .
  • Dual optimum: Choose : constraints and hold, and dual objective is .
Answer:

Weak Duality gives and Strong Duality gives equality at optimality. The dual minimizes subject to . Both achieve the identical optimum at and .

Question 5

Write an Integer Linear Program (ILP) for the Weighted Set Cover problem, state its LP relaxation, and explain how deterministic LP rounding yields a -approximation for Weighted Vertex Cover (why does the proof fail to give a -approximation for general Set Cover?).

ILP and LP relaxation for Weighted Set Cover: Introduce binary variable for each (indicating whether is chosen):

The LP relaxation replaces with (or ).

Why deterministic rounding gives -approx for Weighted Vertex Cover vs. -approx for Set Cover: In Vertex Cover, each edge belongs to at most sets (its two endpoints), so guarantees . Picking every vertex with covers all edges and scales every variable up by at most , giving weight . In general Set Cover, an element can belong to up to sets (), so we can only guarantee some set has , yielding an -approximation rather than a constant factor .

Answer:

Weighted Set Cover minimizes subject to with (relaxed to ). Rounding gives an -approximation where is the maximum element frequency—yielding for Vertex Cover (), whereas general Set Cover has unbounded .

← Parallel and Distributed AlgorithmsOnline and Streaming Algorithms →