Unit 12: Approximation

I. Orientation — Near-Optimal Solutions with Provable Guarantees

Approximation algorithms are polynomial-time methods for optimization problems where finding an exact optimum is computationally infeasible, commonly because the problem is NP-hard. Rather than merely returning a plausible answer, an approximation algorithm supplies a mathematical guarantee comparing its solution with the unknown optimum.

• Optimization problem: Each valid input (I) has a set of feasible solutions and an objective value to minimize or maximize.
• Optimal value: (\operatorname{OPT}(I)) denotes the objective value of the best feasible solution for instance (I).
• Polynomial running time: An approximation algorithm must run in time polynomial in the encoded input size, such as (O(n\log n)) for (n) jobs or items.
• Feasibility: The returned solution must satisfy every constraint; closeness to optimality does not excuse an invalid solution.
• Approximation guarantee: A proven bound limits the worst-case difference between the algorithm’s value and (\operatorname{OPT}(I)).
• Problem direction:
  • For minimization, smaller objective values are better.
  • For maximization, larger objective values are better.
• Common design principles: Greedy selection, ordering, relaxation, rounding, lower bounds, and local improvement are used to obtain efficient solutions.
• Central trade-off: Better solution quality may require additional computation, while faster algorithms may have weaker guarantees.

II. Approximation Basics — Measuring and Designing Near-Optimal Algorithms

A. Approximation basics

Approximation analysis establishes how close a polynomial-time algorithm’s result is to the exact optimum on every valid input.

• Minimization ratio: If an algorithm produces value (A(I)), it is an (\alpha)-approximation when
  

  TEXT

    OPT(I) ≤ A(I) ≤ α · OPT(I)

  
  where (I) is the input instance, (A(I)) is the algorithm’s objective value, (\operatorname{OPT}(I)) is the minimum possible value, and (\alpha \ge 1).

• Maximization ratio: For a maximization problem, the guarantee is
  

  TEXT

    OPT(I) / α ≤ A(I) ≤ OPT(I)

  
  because no feasible solution can exceed the maximum (\operatorname{OPT}(I)).

• Relative error form: A ((1+\varepsilon))-approximation for minimization satisfies
  

  TEXT

    A(I) ≤ (1 + ε) · OPT(I)

  
  where (\varepsilon>0) is the permitted relative error. For example, (\varepsilon=0.05) permits a value at most (5\%) above optimum.

• Absolute versus asymptotic guarantees:

  1. Absolute ratio: The bound applies directly to every instance, including small ones.
  2. Asymptotic ratio: A constant additive term is permitted:
     
     TEXT

          A(I) ≤ α · OPT(I) + β

     
     where (\alpha) is the asymptotic approximation ratio and (\beta) is a fixed constant independent of the input size.

• Lower and upper bounds: Approximation proofs compare the output against a bound that is easier to compute than the optimum.

  • In minimization, a lower bound (L(I)\le \operatorname{OPT}(I)) helps prove (A(I)\le\alpha\operatorname{OPT}(I)).
  • In maximization, an upper bound (U(I)\ge \operatorname{OPT}(I)) plays the corresponding role.

• Worked example: Suppose a minimization algorithm returns a solution of cost (120), while a valid argument proves (\operatorname{OPT}(I)\ge100). Then
  

  TEXT

    A(I) / OPT(I) ≤ 120 / 100 = 1.2

  
  so this instance has a certified ratio of at most (1.2), even though the exact optimum is unknown.

• Approximation scheme:

  • A polynomial-time approximation scheme (PTAS) gives a ((1+\varepsilon))-approximation for every fixed (\varepsilon>0), with polynomial running time in input size.
  • A fully polynomial-time approximation scheme (FPTAS) is polynomial in both input size and (1/\varepsilon).
  • A PTAS may become impractical when (\varepsilon) is small because its exponent can depend on (1/\varepsilon).

B. Design and limitations

An approximation guarantee is a worst-case theorem, not a claim that every returned solution reaches that bound.

• Greedy construction: A locally attractive choice is repeatedly made, as when assigning the next job to the least-loaded machine.
• Relaxation and rounding: Constraints such as integrality are temporarily weakened, the relaxed problem is solved, and fractional values are converted into a feasible discrete solution.
• Charging argument: Parts of the approximate solution’s cost are assigned to components of an optimal solution to show that each optimal component is charged at most (\alpha) times.
• Worst-case interpretation: A 2-approximation may often be optimal in practice; the factor 2 only limits how poor it can be on adversarial instances.
• No universal method: Approximation ratios are problem-specific. An argument valid for scheduling cannot automatically establish a bin-packing bound.
• Hardness barrier: Some NP-hard problems cannot be approximated within particular factors in polynomial time unless standard complexity assumptions, such as (P\ne NP), fail.

III. Task Scheduling — Balancing Work Across Identical Machines

A. Task scheduling

Task scheduling assigns independent jobs to machines so that the completion time of the last machine, called the makespan, is minimized.

• Problem model: For (n) jobs and (m) identical parallel machines, job (j) has processing time (p_j>0), and each job must be assigned wholly to one machine.

• Machine load: If (S_i) is the set of jobs assigned to machine (i), its load is
  

  TEXT

    L_i = Σ(j ∈ S_i) p_j

  
  where (L_i) is machine (i)’s completion time and (S_i) is its assigned job set.

• Objective: The makespan is
  

  TEXT

    Cmax = max(1 ≤ i ≤ m) L_i

  
  where (C{\max}) is the latest machine completion time. The goal is to minimize (C{\max}).

• Fundamental lower bounds:
  

  TEXT

    OPT ≥ (Σ(j=1 to n) p_j) / m
    OPT ≥ max(1 ≤ j ≤ n) p_j

  
  The first bound follows from average load; the second follows because the longest job must run somewhere.

• List scheduling algorithm: Process jobs in a given order and assign each one to a currently least-loaded machine.
  

  TEXT

    initialize load[i] = 0 for each machine i
    for each job j in list order:
        choose i with minimum load[i]
        assign job j to machine i
        load[i] = load[i] + p[j]
    return maximum load

  
  Here, load[i] is machine (i)’s assigned processing time and p[j] is job (j)’s processing time.

• List-scheduling guarantee: For (m) identical machines,
  

  TEXT

    Cmax ≤ (2 - 1/m) · OPT

  
  because the machine receiving the final job previously had load no greater than the average assigned load.

• Longest Processing Time first: LPT sorts jobs in non-increasing processing-time order before applying list scheduling. Its stronger guarantee is
  

  TEXT

    Cmax ≤ (4/3 - 1/(3m)) · OPT

  
  for (m\ge2).

• Worked example: For two machines and job times (5,4,3,3,2), LPT produces loads:

  • Machine 1: (5+3=8).
  • Machine 2: (4+3+2=9).

  The makespan is (9). Since total work is (17), every schedule has makespan at least (\lceil17/2\rceil=9); therefore this schedule is optimal.

B. Applications and limitations

Approximate scheduling is useful when rapid load balancing matters more than the expensive search for an exact partition.

• Applications: Processor allocation, cloud workloads, manufacturing stations, and batch-processing systems all use makespan as a measure of completion speed.
• Efficiency: With a priority queue of machine loads, list scheduling takes (O(n\log m)); LPT additionally sorts jobs, giving (O(n\log n+n\log m)).
• Tie handling: Any least-loaded machine may be selected when loads tie; the approximation guarantee remains valid.
• Model limitations: The stated bounds assume identical machines, independent jobs, no preemption, and known processing times.
• Extended constraints: Deadlines, precedence relations, release times, communication costs, or unrelated machine speeds require different algorithms and analyses.

IV. Bin Packing — Minimizing the Number of Fixed-Capacity Containers

A. Bin packing

Bin packing places indivisible items into the fewest equal-capacity bins without exceeding any bin’s capacity.

• Problem model: Given item sizes (s_1,\ldots,s_n) and bin capacity (B), each item satisfies (0<s_j\le B).

• Feasibility condition: For every bin (k),
  

  TEXT

    Σ(j assigned to bin k) s_j ≤ B

  
  where (s_j) is item (j)’s size and (B) is bin capacity.

• Objective: Minimize the number of nonempty bins. A basic lower bound is
  

  TEXT

    OPT ≥ ceil((Σ(j=1 to n) s_j) / B)

  
  because the total item size must fit within the total capacity of all used bins.

• Next Fit: Keep only one bin open; place the next item there if it fits, otherwise close that bin and open another.

  • Time: (O(n)).
  • Guarantee: Next Fit uses at most (2\operatorname{OPT}-1) bins.

• First Fit: Scan existing bins in creation order and place each item in the first bin with sufficient remaining capacity; open a new bin if none works.

  • Time: (O(n^2)) in a direct implementation.
  • Guarantee: Its asymptotic approximation ratio is (17/10).

• Best Fit: Place each item in a feasible bin that leaves the least remaining capacity, attempting to fill bins tightly.

• First Fit Decreasing: Sort items in non-increasing size order, then apply First Fit.

  • Time: Common implementations run in (O(n\log n)).
  • Bound:
    
    TEXT

        FFD(I) ≤ (11/9) · OPT(I) + 6/9

    
    where (\operatorname{FFD}(I)) is the number of bins used on instance (I).

• Worked example: With (B=10) and item sizes (6,6,4,4,2), First Fit Decreasing packs ((6,4)), ((6,4)), and ((2)), using three bins. Since the total size is (22), the lower bound is (\lceil22/10\rceil=3), proving optimality.

B. Applications and limitations

Bin-packing heuristics convert capacity constraints into fast placements, but their success depends strongly on item order and size distribution.

• Applications: Memory allocation, disk storage, cargo loading, cutting stock, and virtual-machine placement can be modeled using bins and capacities.
• Online versus offline methods:
  1. Online: Next Fit and unsorted First Fit can process items as they arrive without seeing future items.
  2. Offline: First Fit Decreasing requires all sizes in advance but gains a stronger guarantee through sorting.
• Fragmentation: Unused capacity may be spread across several bins even when its total is large enough for another item.
• Order sensitivity: First Fit and Best Fit can produce different packings for different input orders; decreasing-order variants reduce this effect.
• Lower-bound limitation: The total-size bound may be weak because it ignores incompatibility among large items, such as several items each exceeding (B/2).
• Model limitation: Classical bin packing uses one capacity dimension; multidimensional packing with weight, volume, or memory constraints requires separate approximation techniques.