10. Approximation and Parameterized Algorithms

Introduction and Context

Many important optimization problems in computer science are computationally difficult. Problems such as travelling salesperson, set cover, graph coloring, facility location, scheduling, and maximum satisfiability are often NP-hard. For such problems, a polynomial-time algorithm that always returns an optimal solution is unlikely to exist unless P = NP. This does not mean that useful computation is impossible. Instead, algorithm designers change the objective: they may accept a solution that is provably close to optimal, or they may accept exponential behavior only in a carefully controlled parameter.

Approximation algorithms and parameterized algorithms provide two complementary responses to computational hardness. Approximation algorithms sacrifice some solution quality in exchange for polynomial running time and provide a mathematical performance guarantee. Parameterized algorithms retain exact optimality but isolate the exponential component in a parameter that may be small in practical instances. Together, these approaches form an important part of algorithmic decision-making for AI, operations research, data science, and large-scale systems.

The central professional question is not merely whether a problem is hard. It is: what resource can be relaxed or controlled? An organization may tolerate a solution that is within 5 percent of optimum, or it may face instances where the number of facilities, exceptions, or selected features is small. Approximation and parameterization formalize these choices.

Learning Objectives

After studying this chapter, the learner should be able to:

• explain computational hardness and the motivation for non-exact solution methods;
• define approximation ratios, additive error, PTAS, and FPTAS;
• design and analyze greedy, local-search, rounding, and primal-dual approximation algorithms;
• distinguish approximation guarantees for minimization and maximization problems;
• formulate parameterized problems and classify algorithms as FPT or XP;
• apply kernelization, bounded search, branching, and parameterized dynamic programming;
• select an appropriate strategy according to quality requirements, instance structure, and resource constraints;
• evaluate practical, ethical, and operational consequences of near-optimal decisions.

Computational Hardness and the Algorithm Designer’s Choice

An optimization problem consists of a set of feasible solutions, an objective function, and a goal to minimize or maximize that function. Let OPT(I) denote the value of an optimal solution for instance I. An approximation algorithm runs in polynomial time and returns a feasible solution A(I).

For a minimization problem, an algorithm has approximation ratio rho if

A(I) <= rho OPT(I),

for every instance I, where rho is at least 1. For a maximization problem, the guarantee is commonly written as

A(I) >= OPT(I)/rho.

Some literature instead states a maximization guarantee as A(I) >= alpha OPT(I), where alpha lies between 0 and 1. Thus a 0.9-approximation and a ratio of 10/9 express the same type of guarantee under different conventions. The convention must always be stated.

A worst-case guarantee differs from an average-case observation. A heuristic may perform extremely well on typical data but have no formal bound. Approximation analysis establishes a bound for every valid input, although the bound may be conservative in practice.

Parameterized complexity asks a different question. Suppose a problem has input size n and a parameter k. Instead of requiring running time polynomial only in n, we seek a running time of the form

f(k)n^c,

where f depends only on k and c is a constant independent of k and n. Such an algorithm is called fixed-parameter tractable, or FPT. If the running time is n^{f(k)}, the problem belongs to XP with respect to k, but this is generally weaker: the exponent itself grows with the parameter.

Approximation Guarantees and Their Interpretation

A ratio is meaningful only when linked to the objective and problem type. For example, a 2-approximation for vertex cover returns a cover of size at most twice the minimum cover. A 2-approximation for a maximization problem, under the ratio convention, returns a solution worth at least half the optimum. Confusing these interpretations is a common analytical error.

An additive guarantee has the form

A(I) <= OPT(I) + c

for minimization, or an analogous inequality for maximization. Additive guarantees are useful when objective values have a natural scale, but they may be weak for small optimum values. Multiplicative guarantees are generally more robust across scales.

The approximation gap of an algorithm is the distance between its guarantee and exact optimality. A problem may admit a constant-factor approximation, a logarithmic approximation, or no meaningful approximation unless major complexity assumptions fail. For instance, greedy set cover achieves a logarithmic guarantee related to the maximum frequency or universe size, while metric travelling salesperson admits constant-factor methods based on spanning trees and shortcutting.

A reduction can transfer approximation difficulty from one problem to another. Approximation-preserving reductions are used to show that improving a known guarantee may be computationally difficult. Consequently, algorithm selection must consider both what is achievable and what is unlikely to be improved efficiently.

Principal Design Strategies for Approximation

Greedy Construction

Greedy algorithms repeatedly choose the locally most attractive feasible action. Their success depends on a structural argument showing that local progress can be charged against an optimal solution. In set cover, the greedy method repeatedly selects the set covering the largest number of currently uncovered elements, or more generally the best coverage per cost. Its logarithmic guarantee follows from a shrinking-residual argument: when many elements remain, some set in an optimal cover must cover a significant fraction of them.

Greedy methods are attractive because they are simple, scalable, and often easy to implement in distributed systems. However, a greedy choice can create poor later commitments. The proof of a guarantee is therefore essential; intuition alone is not sufficient.

Relaxation and Rounding

Integer programs describe many combinatorial problems. Replacing integrality constraints with continuous constraints produces a linear programming relaxation that can be solved efficiently in many settings. The fractional solution provides a lower bound for minimization problems and an upper bound for maximization problems.

Rounding transforms the fractional solution into a feasible integral solution. In deterministic rounding, variables are rounded according to carefully designed thresholds. In randomized rounding, a variable is selected with a probability related to its fractional value. Expected objective value and constraint-violation bounds are then established, often using concentration inequalities or alteration procedures.

The integrality gap is the worst-case ratio between the integer optimum and the fractional optimum. It limits what a particular relaxation-and-rounding framework can prove. A stronger formulation can reduce the gap but may increase computational cost.

Primal-Dual Design

For problems expressible through a linear program and its dual, primal-dual algorithms gradually raise dual variables until a constraint becomes tight, then construct a primal solution from tight constraints. This approach often yields both an algorithm and a certificate explaining its quality. It is especially influential in covering, facility location, network design, and scheduling.

The method is valuable in practice because dual variables can have operational interpretations: they may represent prices, resource scarcity, or the marginal value of satisfying a requirement. Such interpretations support sensitivity analysis and managerial explanation.

Local Search

Local search begins with a feasible solution and repeatedly applies an improving local modification. A solution is locally optimal when no allowed neighborhood move improves it. The approximation guarantee depends on the neighborhood definition and on inequalities relating local optimality to global optimality.

For metric facility location, clustering, and routing, local search can provide strong practical performance. Its limitations include dependence on the initial solution, possible local optima, and potentially high running time when neighborhoods are large. Multiple restarts, efficient move evaluation, and hybridization with exact or randomized methods can improve performance.

Dual Fitting and Charging Arguments

In dual fitting, an algorithm implicitly constructs dual variables that may violate constraints by a bounded factor. Scaling them produces a feasible dual solution. Weak duality then proves the approximation ratio. Charging arguments use a related idea: the cost of algorithmic decisions is assigned to elements or structures in an optimal solution, with each optimal component charged only a bounded number of times.

These proof techniques are not merely formal. They reveal which input features cause poor performance and can guide improved variants.

Approximation Schemes

A polynomial-time approximation scheme, or PTAS, is a family of algorithms indexed by epsilon > 0. For every fixed epsilon, the algorithm returns a solution within a factor of 1 + epsilon for minimization, or at least 1 - epsilon times optimum for maximization, and runs in polynomial time in n. The exponent of n may depend on epsilon.

A fully polynomial-time approximation scheme, or FPTAS, is stronger: its running time is polynomial in both n and 1/epsilon. FPTAS methods commonly arise through scaling and dynamic programming. For example, profit scaling can convert a knapsack instance into one whose dynamic-programming state space depends polynomially on 1/epsilon.

The distinction matters operationally. A PTAS with running time n^{1/epsilon} may become impractical when high accuracy is required. An FPTAS offers better control of the accuracy-time trade-off, although its polynomial factors may still be large.

Approximation schemes are not available for every NP-hard problem unless major complexity consequences follow. For some problems, geometric structure permits a PTAS through partitioning and dynamic programming. For others, strong inapproximability results rule out schemes under standard assumptions. Therefore, one must not treat epsilon as a universal solution to hardness.

Parameterized Complexity: Exactness with a Controlled Exponential Component

A parameterized problem is written as a pair (I, k), where k measures a selected structural feature. The parameter may be the desired vertex-cover size, the number of clusters, the number of machine types, the solution size, treewidth, or the number of allowed exceptions. Good parameterization is problem-dependent and should reflect a quantity expected to be small or structurally informative.

An FPT algorithm has running time f(k)n^{O(1)}. The function f(k) may be exponential, but it does not affect the polynomial degree in n. This is valuable when k is small even if the overall data set is large. By contrast, an XP algorithm with time n^{k} may be unusable when n is large, despite being polynomial for every fixed k.

Kernelization

Kernelization is a polynomial-time preprocessing procedure that maps (I, k) to an equivalent instance (I', k') whose size is bounded by a function g(k). The reduced instance is called a kernel. After solving the kernel, the result is translated back to the original instance.

For vertex cover, repeated reduction rules can remove isolated vertices, include vertices of sufficiently high degree, and simplify dominated structures. A kernel reduces the burden on subsequent branching or exact search. Kernelization is also a practical engineering technique: preprocessing can substantially improve an algorithm even when theoretical guarantees are not the primary goal.

Bounded Search Trees

A bounded search algorithm branches on a limited set of alternatives. If each branch reduces the parameter by at least a known amount, a recurrence such as T(k) <= T(k-1) + T(k-2) leads to a running-time bound of the form O(c^k n^d). Branching rules should be chosen to minimize the branching factor and maximize parameter reduction.

For vertex cover, selecting an edge (u, v) creates two branches: include u or include v. Each branch decreases the required cover size by one. More sophisticated branching based on vertex degree gives improved bounds.

Parameterized Dynamic Programming

When a graph has small treewidth, dynamic programming over a tree decomposition can solve problems that are difficult on unrestricted graphs. The state records only the information needed at a boundary between processed and unprocessed portions. The exponential dependence is placed on treewidth rather than on total graph size.

This illustrates a broad principle: apparent global complexity may become manageable when the instance has limited structural interaction. Similar ideas use pathwidth, feedback vertex set, solution size, or the number of distinct weights as parameters.

Parameterized Intractability

Not every natural parameter yields an FPT algorithm. The W-hierarchy, including classes such as W[1] and W[2], provides evidence that certain parameterized problems are unlikely to be FPT. A parameterized reduction transforms one problem into another while controlling the parameter. Such reductions guide researchers and practitioners away from unrealistic algorithmic expectations.

Choosing Between Approximation and Parameterization

The choice depends on the decision environment. Approximation is appropriate when instances are large, near-optimal solutions are acceptable, and a predictable quality bound is required. Parameterization is appropriate when exactness matters and a meaningful parameter is small. A hybrid method may first kernelize an instance, then apply approximation to a remaining subproblem, or use an FPT algorithm when k is below a threshold and a heuristic otherwise.

Important selection criteria include:

• the required quality tolerance;
• the size and distribution of input instances;
• whether a small structural parameter exists;
• the cost of implementation and explanation;
• worst-case versus empirical performance;
• memory, latency, and energy constraints;
• the consequences of violating constraints or making poor decisions.

In AI and ML, approximation is common in feature selection, submodular maximization, resource allocation, recommendation diversification, graph summarization, and large-scale clustering. Parameterized methods are relevant to interpretable model construction, small-exception classification rules, motif discovery, constrained feature selection, and graph-based learning with bounded structural complexity.

An Illustrative Case Study: Emergency Facility Placement

Background

Consider a regional emergency-management agency that must select locations for a limited number of response stations. Each demand point has a service requirement, and opening a station incurs a fixed cost. The objective is to cover demand at minimum cost while respecting service-distance constraints. This is a covering and facility-location problem and is generally computationally difficult.

Situation and Analysis

The agency receives thousands of demand points, so exact integer programming may exceed the response-time budget. However, decision makers require a defensible quality guarantee. A greedy method could repeatedly open the station covering the largest amount of uncovered demand per unit cost. This is fast, but its guarantee depends on the precise formulation and may be weak when costs vary substantially.

The analysts formulate a linear programming relaxation. Each candidate station has a fractional opening variable, and each demand point has a fractional assignment variable. Solving the relaxation supplies a bound on the optimum. Randomized rounding then opens stations with probabilities derived from fractional values. If some demand remains uncovered, an alteration step adds carefully selected stations.

Strategy and Solution

The final method combines three stages. First, geographic preprocessing removes dominated candidate sites: if one site is no more expensive and covers every point covered by another, the weaker site can be discarded. Second, the relaxation is solved to obtain a lower bound and fractional structure. Third, rounding and local improvement produce an integral solution. The local-search phase exchanges one or more opened stations for alternatives that reduce cost without losing required coverage.

For small districts, where the number of candidate sites is limited, the agency also runs an exact parameterized procedure with the number of opened stations as parameter. Large districts use the approximation method; small, high-priority districts use the exact method.

Outcome

The hybrid design gives rapid solutions for large regions, a measurable bound relative to the relaxation-based analysis, and exact answers for selected small regions. More importantly, the agency can explain why a site was chosen: coverage contribution, dual scarcity values, and exchange improvements are all recorded.

Learning Points

The case demonstrates that algorithm selection is a portfolio decision rather than a contest between one “best” algorithm and all others. Approximation provides scalability and assurance; parameterization provides exactness when structure permits it; preprocessing and local improvement enhance both. The case also shows why operational constraints, interpretability, and response time belong in algorithm analysis.

Limitations, Risks, and Common Mistakes

A formal approximation ratio may be too pessimistic for ordinary instances, while empirical performance without a proof may fail catastrophically on unusual inputs. Another mistake is comparing ratios across different objective scales or using a minimization guarantee as though it were a maximization guarantee.

Relaxation-based methods can suffer from a large integrality gap. Randomized rounding may violate service or safety constraints unless alteration and concentration analysis are included. Greedy algorithms can be sensitive to tie-breaking and data ordering. Local search may terminate at a poor local optimum, and parameterized algorithms may become impractical when the parameter is not actually small.

Parameter choice itself can be misleading. A parameter that appears conceptually small may grow with n in real data. Kernelization may reduce instance size but still leave an exponential kernel-solving step. Memory requirements, parallelization overhead, numerical precision, and dynamic input changes must also be evaluated.

Ethical, Governance, and Professional Considerations

Approximate decisions in healthcare, emergency response, lending, hiring, or public services can affect people unequally. A mathematically bounded objective does not guarantee fairness, safety, or legal compliance. The objective function may omit vulnerable populations, accessibility, environmental effects, or distributional equity.

Practitioners should document the optimization objective, approximation guarantee, parameter choice, stopping conditions, data assumptions, and fallback behavior. Constraints with ethical or regulatory significance should be hard constraints rather than soft penalties whenever appropriate. Auditing should examine whether approximation errors are concentrated in particular groups or regions. Human review is essential when a near-optimal mathematical solution could create unacceptable real-world harm.

Current Developments and Best Practices

Modern work increasingly combines approximation with machine learning. Learned heuristics can predict promising greedy choices, branching variables, or local-search neighborhoods, while a classical algorithm retains feasibility checks and, where possible, a formal guarantee. This creates a useful separation: learning guides search, whereas the algorithmic framework controls correctness.

Other developments include distributed and streaming approximation for massive data, approximation under differential privacy, fair and robust optimization, and parameterized algorithms for graph problems in temporal, uncertain, or multilayer networks. Fine-grained complexity is also refining lower bounds by relating improvements in running time to conjectures about problems such as satisfiability.

Best practice is to begin with a precise formulation and a baseline. Establish lower and upper bounds, identify exploitable structure, and choose a parameter or tolerance that has operational meaning. Then combine preprocessing, a provable core method, and empirical evaluation on representative and adversarial instances. Report both quality and resource usage. Finally, test sensitivity: a method that is excellent for epsilon = 0.1 may be unusable for epsilon = 0.01, and an FPT algorithm that works for k = 5 may fail for k = 25.

Chapter Summary

Approximation algorithms address NP-hard optimization by returning efficiently computed solutions with provable quality guarantees. Greedy, relaxation-and-rounding, primal-dual, local-search, dual-fitting, and charging methods are major design approaches. PTAS and FPTAS frameworks provide increasingly accurate solutions, with FPTAS offering polynomial dependence on both input size and inverse accuracy.

Parameterized algorithms retain exactness by confining exponential computation to a parameter. FPT algorithms run in f(k)n^{O(1)}, while XP algorithms have a parameter-dependent exponent. Kernelization, bounded search trees, and parameterized dynamic programming are central techniques. Approximation and parameterization are complementary and may be combined in practical systems. Sound algorithm selection requires attention to guarantees, structural parameters, scalability, interpretability, fairness, safety, and the consequences of error.

Key Terms

Approximation algorithm: A polynomial-time algorithm that returns a solution with a guaranteed relationship to the optimum.

Approximation ratio: The worst-case multiplicative comparison between an algorithm’s solution and the optimal solution.

Additive guarantee: A bound expressed as a fixed amount added to or subtracted from the optimum.

PTAS: A polynomial-time approximation scheme that achieves any fixed accuracy level, with polynomial time for each fixed epsilon.

FPTAS: An approximation scheme polynomial in both input size and 1/epsilon.

Integrality gap: The worst-case difference between an integer optimization problem and its continuous relaxation.

Linear programming relaxation: A formulation obtained by replacing integer restrictions with continuous constraints.

Randomized rounding: Converting fractional variables into integral choices using probabilities.

Primal-dual algorithm: A method that constructs or uses feasible relationships between primal and dual optimization formulations.

Local search: Improvement through repeated changes within a specified neighborhood of solutions.

Charging argument: A proof technique assigning algorithmic cost to optimal structures in a bounded way.

Parameterized problem: A problem instance accompanied by a parameter measuring a relevant structural feature.

FPT: Fixed-parameter tractable; solvable in f(k)n^{O(1)} time.

XP: A parameterized class containing algorithms with running time n^{f(k)}.

Kernelization: Polynomial preprocessing that produces an equivalent instance bounded in size by a function of the parameter.

Kernel: The reduced instance produced by kernelization.

Bounded search tree: A recursive algorithm whose branching and parameter reduction yield a controlled exponential bound.

Treewidth: A graph parameter measuring how close a graph is to a tree-like structure.

Approximation-preserving reduction: A reduction that transfers approximation relationships between problems.

W-hierarchy: A framework expressing evidence that some parameterized problems are unlikely to be FPT.

Review Questions

Short Answer Questions

1. What is the difference between a multiplicative approximation guarantee and an additive guarantee?

2. Define an FPT algorithm and contrast it with an XP algorithm.

3. What is the purpose of an integrality gap analysis?

4. Explain the role of kernelization in parameterized algorithms.

5. Why must approximation ratios for minimization and maximization be interpreted differently?

Long Answer Questions

1. Explain greedy, relaxation-and-rounding, primal-dual, and local-search methods, including the type of reasoning used to prove their guarantees.

2. Compare PTAS and FPTAS with respect to accuracy and running-time dependence.

3. Describe bounded search trees and parameterized dynamic programming as approaches to exact computation.

4. Discuss how approximation and parameterization can be combined in an operational decision system.

5. Analyze the ethical and governance issues that arise when approximate algorithms are used in public-service allocation.

Analytical / Application Questions

1. A minimization algorithm returns a solution of cost 120, while a lower bound from a relaxation is 100. What guarantee can be inferred from this bound, and what additional information is needed to claim a guarantee relative to the true optimum?

2. An exact algorithm runs in O(2^k n^3), where k is the number of selected facilities. For what type of data would this method be preferable to a constant-factor approximation, and why?

3. Design a hybrid strategy for a large graph problem in which most instances have small treewidth but a minority do not. Explain preprocessing, algorithm selection, fallback behavior, and evaluation criteria.

22. Multiple Choice Questions with Answers

Question 1

For a minimization problem, which statement correctly expresses a rho-approximation guarantee?

A. A(I) >= rho OPT(I)

B. A(I) <= rho OPT(I)

C. A(I) = OPT(I) for every instance

D. A(I) <= OPT(I) - rho

Correct Answer: B. A(I) <= rho OPT(I)

Question 2

Which running time characterizes a fixed-parameter tractable algorithm with parameter k?

A. n^k

B. 2^n k^3

C. f(k)n^c

D. n + log k

Correct Answer: C. f(k)n^c

Question 3

What is the principal advantage of an FPTAS over a PTAS?

A. It always returns an exact optimum

B. Its running time is polynomial in both n and 1/epsilon

C. It applies to every NP-hard problem

D. It has no dependence on epsilon

Correct Answer: B. Its running time is polynomial in both n and 1/epsilon

Question 4

In a linear-programming approximation method, the fractional optimum for a minimization problem is generally what?

A. An upper bound on the integer optimum

B. A lower bound on the integer optimum

C. Always equal to the integer optimum

D. An infeasible solution with no analytical value

Correct Answer: B. A lower bound on the integer optimum

Question 5

A parameterized algorithm with running time n^{k+2} is generally classified as which type with respect to k?

A. FPT

B. FPTAS

C. XP

D. PTAS

Correct Answer: C. XP

Question 6

What does kernelization produce?

A. A randomly rounded solution

B. An equivalent instance whose size is bounded by a function of the parameter

C. A solution guaranteed to be globally optimal without further computation

D. A relaxation with all integrality constraints removed

Correct Answer: B. An equivalent instance whose size is bounded by a function of the parameter

Question 7

Which situation most strongly favors an approximation algorithm over an exact parameterized algorithm?

A. The parameter is demonstrably small and exactness is mandatory

B. The instance is huge and a bounded loss in quality is acceptable

C. The graph has treewidth two

D. The desired solution size is at most three

Correct Answer: B. The instance is huge and a bounded loss in quality is acceptable

Question 8

What is the main purpose of a charging argument in approximation analysis?

A. To assign algorithmic cost to optimal structures in a bounded manner

B. To eliminate all constraints from an optimization model

C. To prove that every local optimum is globally optimal

D. To convert an XP algorithm into an FPT algorithm automatically

Correct Answer: A. To assign algorithmic cost to optimal structures in a bounded manner

Question 9

In randomized rounding, why may an alteration step be required?

A. To increase the input size

B. To restore feasibility if randomized choices leave constraints unsatisfied

C. To remove the approximation guarantee

D. To make the algorithm exponential in n

Correct Answer: B. To restore feasibility if randomized choices leave constraints unsatisfied

Question 10

Which governance practice is most appropriate when approximation is used for emergency-service allocation?

A. Report only average performance and omit the objective function

B. Treat mathematical optimality as a substitute for fairness review

C. Document guarantees, constraints, assumptions, and possible unequal impacts

D. Use a learned heuristic without feasibility checks

Correct Answer: C. Document guarantees, constraints, assumptions, and possible unequal impacts