Design and Analysis of Algorithms

Answer: (i) 2

Explanation:

• Classic 2-approximation for Minimum Vertex Cover (greedy matching-based):

  C = ∅
  while E ≠ ∅:
    pick any edge (u,v) ∈ E
    add both u and v to C
    remove all edges incident to u or v
  

  Any optimal cover must include at least one endpoint of each picked edge, and picked edges are disjoint. So $|C| ≤ 2·|OPT|$.

• Ratio 2 is tight; a simple maximal-matching algorithm achieves it. No polynomial algorithm can achieve $(2-\epsilon)$ unless $P=NP$ (inapproximability). The naive greedy "pick highest-degree vertex" can be $\Theta(\log n)$ bad, not 2.

Correct choice: (i) 2

Answer: (ii) Random choices during execution

Explanation:

• Randomized algorithms use a random number generator to make decisions; behavior is probabilistic.
• Types: Las Vegas (always correct, random running time, e.g., Randomized QuickSort) vs Monte Carlo (may be incorrect with bounded probability, e.g., Miller-Rabin primality).
• Random choices help avoid worst-case inputs (Randomized QuickSort expected $O(n \log n)$) or achieve simplicity/probabilistic guarantees.

Correct choice: (ii)

Approximation Algorithm for TSP (Metric TSP — 2-Approximation)

For general TSP (arbitrary distances) no polytime approximation exists unless $P=NP$ (Hamiltonian cycle reduces). For Metric TSP (complete graph satisfying triangle inequality $c(u,w) ≤ c(u,v)+c(v,w)$) a constant-factor approximation exists.

2-Approximation via MST ( MST-doubling )

Approx-TSP(G, c):
  T = MST(G)  // via Prim/Kruskal $O(E\log V)$
  Perform preorder walk of T (DFS) starting at arbitrary root, list vertices in order of first visit
  Return Hamiltonian cycle visiting in that order + return to start (shortcutting repeated vertices using triangle inequality)

Analysis: Let OPT = optimal TSP tour cost. Removing one edge from OPT gives spanning tree → $c(T) ≤ c(OPT)$. Full walk of T traverses each edge twice → $c(W)=2c(T) ≤2c(OPT)$. Shortcutting via triangle inequality can only decrease cost → $c(H) ≤c(W) ≤2c(OPT)$ → 2-approximation. Time $O(V^2)$ or $O(E\log V)$.

Christofides 1.5-Approximation (better)

1. Find MST $T$.
2. Find minimum weight perfect matching $M$ on vertices of $T$ with odd degree (even number, via Blossom $O(V^3)$).
3. Combine $T∪M$ (Eulerian multigraph, all vertices even degree).
4. Find Euler tour, shortcut to Hamiltonian cycle.
   Ratio: $c(T)≤OPT$, $c(M)≤OPT/2$ → $c(H)≤1.5 OPT$.

Heuristic without guarantee: Nearest Neighbor, 2-opt local search.

Approximation for NP-Hard Optimization — General Steps + Example

Why Approximation?

NP-hard optimization (e.g., TSP, Vertex Cover, Set Cover, Knapsack) no known polytime exact solution (if $P
eq NP$). Approximation algorithms give near-optimal feasible solution in polytime with proven ratio guarantee.

General Steps

1. Formulate optimization: Min or Max objective (e.g., min vertex cover size, min tour length).
2. Check complexity: Prove NP-hard (reduction from known NP-hard). → motivates approximation.
3. Design polytime heuristic: Often greedy, DP relaxation, LP rounding, MST/matching, local search.
4. Prove approximation ratio $\rho$:
   • For minimization: $\frac{ALG}{OPT} \le \rho$
   • For maximization: $\frac{OPT}{ALG} \le \rho$
     Show bound via lower bound on OPT (e.g., LP optimum ≤ OPT, MST ≤ TSP OPT) and upper bound on ALG.
5. Analyze time: Must be polytime (e.g., $O(n\log n)$, $O(n^3)$).
6. Tighten: Improve ratio or show hardness of better approximation (inapproximability).

Example: Minimum Vertex Cover — 2-Approximation

Input graph $G(V,E)$, goal min vertices covering all edges.

Algorithm (matching-based, as in Q84):

C=∅; E' = E
while E'≠∅:
  pick arbitrary (u,v)∈E'
  C = C ∪ {u,v}
  remove all edges incident to u or v from E'
return C

Proof of ratio 2: Let $M$ be set of edges picked (matching, disjoint). Any vertex cover must include ≥1 endpoint per edge in $M$ → $OPT ≥ |M|$. Algorithm includes both endpoints → $|C|=2|M| ≤2·OPT$.

Example graph: Triangle $a-b, b-c, c-a$. $M$ picks $(a,b)$ → $C={a,b}$ size2, OPT=2 (any 2 cover) ratio1. Star center+leaves: picks center-leaf → $C$ size2 vs OPT1 → ratio2 tight.

Time $O(V+E)$.

Other examples: Metric TSP 2-approx via MST (Q96), Knapsack FPTAS, Set Cover $\ln n$ greedy.

Importance: Provides usable solutions with guarantee where exact is infeasible.

Bin Packing Problem & Heuristics

Problem

Given items sizes $s_i ∈ (0,1]$ (bin capacity 1) or integer capacity $C$, pack into minimum number of bins. Decision version NP-complete (reduction from Partition), optimization NP-hard. No known polytime exact → heuristics & approximation.

Heuristics (online — items appear one by one)

First Fit (FF): For each item in given order, place in first bin where it fits (scanning bins in order); if none, open new bin.

• Time $O(n\log n)$ or O(n·#bins).
• Approximation: $FF ≤ 1.7·OPT +1$ (Johnson), uses at most $⌈1.7 OPT⌉$ bins.

Best Fit (BF): Place item in bin where it leaves smallest leftover space that still fits (tightest fit); if none, new bin.

• Also ~1.7 approx. Often better in practice than FF on average, but worst similar.
• Needs searching bins by leftover.

Next Fit (NF): Keep only current bin open; if item doesn't fit current, close it and open new bin (don't look back).

• Simplest $O(n)$, but worst $2·OPT -1$ (factor 2, worse than FF/BF). Example: items $0.5,0.5,0.5,0.5$ → NF uses 4 bins vs OPT2? Actually NF: bin1:0.5+0.5 fits →2 items per bin →2 bins optimal; worst case alternating 0.6,0.4 etc shows gap.

Sorted variants: First Fit Decreasing (FFD), Best Fit Decreasing (BFD) sort items descending first → improves to $11/9 OPT +1$ (~1.22) for FFD/BFD, best among simple heuristics.

Example $C=10$, items 6,6,5,5,4,4,4:

• NF: Bin1 6 → next6 no fit → Bin2 6, 5 no→Bin3 5,4 fits→5+4=9, next4 no→Bin4 4,4→8 → total4 bins
• FF: Bin1 6+4=10, Bin2 6+4=10, Bin3 5+5=10, Bin4 4→4 bins optimal =4
• BF similar 4.

Optimal is NP-hard; heuristics give fast near-optimal packing used in memory allocation, cutting stock, scheduling.

Short Notes

(a) Cook's Theorem (see Q86/Q72)

SAT is first NP-complete problem (1971 Cook-Levin). Every $L∈NP$ reduces to SAT via tableau encoding of nondet TM computation into poly-size CNF formula $φ_x$ with variables for tape/head/state over time steps $p(n)$. SAT∈NP via assignment verifier. Consequence: $P=NP ⇔ SAT∈P$; Karp reduced SAT to 21 other problems proving NP-completeness pervasive. Foundations of complexity and hardness proofs.

(b) Randomized Algorithms (see Q59/Q74)

Use random choices; types Las Vegas (always correct, random time, e.g., Randomized Quicksort expected $O(n\log n)$) vs Monte Carlo (bounded error, e.g., Miller-Rabin primality). Techniques: random sampling, hashing, random pivot. Expected time analysis via linearity of expectation. Power: avoid worst-case inputs, simple, often faster average. Derandomization open.

(c) Bin Packing (see Q99)

Items sizes $∈(0,1]$, bins capacity1, minimize bins — NP-hard (reduction from Partition). Heuristics: Next Fit (factor2, $O(n)$), First Fit & Best Fit (1.7 approx, $O(n\log n)$), First Fit Decreasing / Best Fit Decreasing sorted (11/9≈1.22 approx, best simple). Applications: cutting stock, memory allocation, scheduling. No PTAS with ratio <3/2 unless $P=NP$; but asymptotic PTAS exists.

Randomized Algorithms & Randomized Quicksort

(i) Randomized Algorithms (as in Q59)

Algorithms using random bits to make decisions; behavior probabilistic. Las Vegas always correct, running time random (e.g., Randomized QuickSort, Skip List). Monte Carlo may be incorrect with bounded probability (e.g., Miller-Rabin). Usage: avoid adversary, simple, expected guarantees.

(ii) Randomized Quicksort Algorithm

RandomizedQuicksort(A, low, high):
  if low < high:
    p = RandomizedPartition(A, low, high) // random pivot
    RandomizedQuicksort(A, low, p-1)
    RandomizedQuicksort(A, p+1, high)

RandomizedPartition(A, low, high):
  i = Random(low, high)  // uniform
  swap A[i], A[high]
  return Partition(A, low, high) // Lomuto/Hoare as in Q14

Alternative: pick random pivot internally without swap.

(iii) Time Complexity

• Worst-case still $Θ(n^2)$ but probability extremely low (requires always bad pivot). No adversary can force it (random pivot independent of input order).
• Expected (over random choices) $Θ(n \log n)$ for any input. Proof: expected partition splits balanced on average; linearity of expectation over comparisons → $E[T(n)] = 2/n \sum_{k} E[T(k)] + Θ(n)$ solves to $Θ(n\log n)$.
• Best $Θ(n\log n)$.
• Space $O(\log n)$ expected stack depth.

Randomization converts worst-case $O(n^2)$ on sorted input (deterministic pivot last) into expected $O(n\log n)$ universally.

Heuristics — Characteristics & Application Domains

What is a Heuristic?

Problem-solving technique using practical, rule-of-thumb, or educated-guess approach that is not guaranteed optimal but gives good enough quickly for hard (often NP-hard) problems. Heuristics trade optimality for speed/feasibility.

Characteristics

• No guarantee of optimal or bounded approximation (vs approximation algorithm has ratio bound; heuristic may be unbounded).
• Problem-specific knowledge embedded (e.g., nearest neighbor for TSP).
• Fast, simple — polytime, often $O(n\log n)$ or $O(n^2)$, usable where exact exponential infeasible.
• Empirically good — works well on typical instances despite worst pathological cases.
• No need to prove ratio — evaluated by experiments/benchmarks.
• Can be combined with metaheuristics (simulated annealing, genetic algorithms, tabu search) for improvement.

vs Approximation Algorithms

Heuristic	Approximation Algorithm
No proven bound	Proven ratio $ρ$ guarantee
Often faster/simpler	May be more complex (LP rounding)
Used when bound not needed	Used when guarantee required

Application Domains

• Combinatorial Optimization: TSP (nearest neighbor, 2-opt), Knapsack (greedy ratio), Bin Packing (FF/BF), Graph Coloring (greedy ordering), Vertex Cover (max degree greedy), Scheduling (list scheduling LPT).
• AI Search: A* heuristic $h(n)$ (admissible Manhattan distance for 8-puzzle, Euclidean for pathfinding) — guides search.
• Routing & Networks: Vehicle routing, network design.
• Resource Allocation: Task scheduling, load balancing, memory allocation.
• Machine Learning: Feature selection heuristics, decision tree splits (information gain).

Examples: Bin Packing First Fit, TSP nearest neighbor tour, Sudoku backtracking with MRV heuristic.

Approximation Algorithms — Importance & Vertex Cover Application

(i) Approximation Algorithms

Polytime algorithms that produce feasible solution with proven distance from optimum. For minimization minimization: $ALG ≤ ρ·OPT$; for maximization $OPT ≤ ρ·ALG$; $ρ≥1$ approximation ratio (performance guarantee). Contrasts with heuristics (no guarantee).

Examples: Metric TSP 2-approx (MST doubling), Christofides 1.5, Set Cover $\ln n$, Knapsack FPTAS.

(ii) Importance for NP-Hard Optimization

• Exact polytime impossible unless $P=NP$ → need alternative for large instances.
• Provides usable solution with confidence bound; helps decide tradeoff speed vs quality.
• Underpins theoretical classification: APX, PTAS, FPTAS hierarchy shows which problems approximable arbitrarily well.
• Guides practice: if problem hard to approximate (e.g., Clique within $n^{1-ε}$ hard), don't waste effort seeking good approx; use heuristic/exponential exact for moderate $n$.

Without approximation, only brute $O(2^n)$ exact feasible for tiny $n$; approximation scales to thousands.

(iii) Applied to Vertex Cover

Minimum Vertex Cover: min vertices covering all edges — NP-hard (reduction from 3-SAT).

2-Approximation (as in Q84/Q97):

C=∅; E' =E
while E'≠∅: pick any (u,v)∈E'; C∪={u,v}; remove all edges incident to u or v

Matching $M$ picked disjoint → $OPT ≥|M|$ (need one per edge) → $|C|=2|M| ≤2 OPT$ → ratio2.

Example: Path $a-b-c-d$. Pick $(a,b)$ → $C={a,b}$, remove edges $ab,bc$ → remaining $c-d$ → pick $(c,d)$ → $C={a,b,c,d}$ size4 vs OPT2 ($b,c$) → ratio2 tight for path? star gives ratio2 worst.

Hardness: Assuming Unique Games, no polytime $(2-ε)$ approx for vertex cover — so this simple 2-approx is essentially best possible.

Thus approximation bridges intractability and practical need.