Approximation and Parallel Algorithms

In the study of computational complexity, we encounter problems that are NP-hard, meaning no known
polynomial-time algorithm can find their exact optimal solution. To address these, we shift our goal from
finding the perfect solution to finding a good solution efficiently. This module explores the mathematical
frameworks for Approximation Algorithms, the intuition of Local Search, and the architectural shift
toward Parallel Algorithms.

1. Fundamentals of Approximation Algorithms

An Approximation Algorithm is a polynomial-time procedure that produces a solution guaranteed to be

within a specific factor of the optimal solution. Unlike heuristics, which might work well in practice but
lack guarantees, approximation algorithms are backed by rigorous mathematical proofs.

 The Approximation Ratio ( ρ ): For a maximization problem, if the algorithm returns a value
S O L and the true optimum is O P T , the ratio is defined such that:
1
SOL≥ ·O PT
ρ
For a minimization problem (e.g., Vertex Cover), the ratio is:
S O L ≤ ρ· O P T
where ρ ≥ 1. A “2-approximation” means the solution is at most twice the cost of the optimum.
2. Linear Programming (LP) and Relaxation

One of the most powerful tools for designing approximation algorithms is Linear Programming
Relaxation. Most NP-hard problems can be modeled as Integer Linear Programs (ILPs), where
variables must be integers (often 0 or 1).

 The Workflow:
1. Formulate the ILP: Define the objective and constraints using integer variables.

2. Relax to LP: Allow the variables to take any real value between 0 and 1. This “relaxed” version
can be solved in polynomial time.

3. Rounding: Convert the fractional values back to integers (0 or 1) while ensuring the solution
remains feasible and close to the LP optimum.

Example: The Vertex Cover Problem Given a graph G=(V , E), find the smallest set of vertices such
that every edge is incident to at least one vertex in the set.
  ILP Formulation: Minimize ∑ x v subject to x u + x v ≥ 1 for every edge (u , v )∈ E, where
v ∈V

x v ∈ {0 ,1 }.

 LP Relaxation: Change the constraint to 0 ≤ x v ≤ 1.

 Rounding Strategy: If the LP solver gives x v ≥0.5 , set x v =1. Otherwise, set x v =0 . Since
x u + x v ≥ 1, at least one of them must be ≥ 0.5. Thus, every edge is covered. This yields a 2-
approximation.

3. The Primal-Dual Method

The Primal-Dual Method is a more sophisticated framework that avoids solving the full LP. Instead, it
uses the relationship between a “Primal” problem (the original minimization) and its “Dual” problem (a
maximization that provides a lower bound).

 Duality Theory: In linear programming, every minimization problem has a corresponding dual
maximization problem. The Weak Duality Theorem states that any feasible solution to the dual
provides a lower bound for the primal optimum ( D ≤ P ).

 The Algorithm Schema:

1. Start with a dual solution of 0 and an empty primal solution.

2. Iteratively increase dual variables (raising the lower bound) until a constraint in the dual becomes
“tight” (reaches its limit).

3. Pick the corresponding primal variable and add it to the solution.

4. Repeat until the primal solution is feasible.

This method is highly efficient for problems like Set Cover and the Generalized Steiner Tree.
4. Local Search Heuristics

Local Search is an iterative improvement strategy. It starts with an arbitrary solution and moves to a
“neighboring” solution if it improves the objective function.

 Key Components:

 Search Space: The set of all possible solutions.

 Neighborhood Function: A rule defining which solutions are “close” to each other (e.g.,
swapping two cities in a Traveling Salesperson Problem tour).

 Local Optimum: A solution that is better than all its neighbors but not necessarily the global
best.

Example: Max-Cut Partition vertices into two sets A and B to maximize edges between them. A local
search would move a vertex from A to B if it increases the number of crossing edges. This simple logic
guarantees a 0.5-approximation.
5. Parallel Algorithms and the PRAM Model

When we move from sequential to parallel computing, we use the PRAM (Parallel Random Access
Machine) model. It consists of multiple processors sharing a single memory.

 Memory Access Variations:

 EREW (Exclusive Read Exclusive Write): Most restrictive; no two processors can access the same
memory cell simultaneously.

 CREW (Concurrent Read Exclusive Write): Multiple processors can read the same cell, but only
one can write.

 CRCW (Concurrent Read Concurrent Write): Most powerful; multiple processors can read and
write to the same cell (requires a protocol to handle write conflicts).

Basic Techniques:

 Pointer Jumping (List Ranking): Used to find the distance of every node in a linked list from the
end. In each step, every node i updates its “next” pointer to n e x t [n e x t [i]]. This reduces the
distance logarithmically, achieving O(log n) time with n processors.
6. Parallel Sorting and Searching

Parallelizing standard algorithms requires rethinking data movement.

 Bitonic Sort: A comparison-based sorting algorithm designed for parallel hardware. It works by
recursively creating “bitonic” sequences (sequences that increase then decrease) and merging
2
them. It has a parallel time complexity of O( log n).
 Parallel Merging: To merge two sorted lists A and B in parallel, we can use Ranking. For each
element in A , we use binary search to find its rank (position) in B. The final position of A [i] is
i+rank (A [i], B).
7. Interconnection Networks

In real-world parallel systems, processors are connected via specific topologies. We evaluate these based
on:

 Diameter: The maximum distance between any two nodes (lower is better).
  Bisection Bandwidth: The minimum number of links to cut to divide the network into two equal
halves (higher is better for communication).

Common Topologies:

1. Mesh: Nodes arranged in a 2D grid. Simple but has a large diameter (O( √ n)).

2. Hypercube: An n -dimensional cube. For N=2

k
nodes, the diameter is only k =log N . It is highly

efficient but complex to wire as N grows.

3. Butterfly: Used in Fast Fourier Transform (FFT) hardware, providing a balance between
connectivity and cost.

Network Diameter Bisection Bandwidth

Linear Array n−1 1
2D Mesh 2( √ n −1) √n
Hypercube log 2 n n /2
By combining these approximation techniques with parallel architectures, we can tackle massive,
complex problems that are otherwise computationally unreachable.