Approximation, Parameterized and Heuristic Algorithms

Introduction

Many important optimization problems are computationally difficult. In complexity theory, problems such as Travelling Salesperson, Knapsack, Set Cover, Maximum Satisfiability and graph coloring are commonly associated with NP-hardness. For such problems, an exact algorithm may require exponential time unless a major unresolved complexity-theoretic conjecture is false. Yet practical systems still need good solutions, often within seconds or minutes and sometimes for instances containing millions of variables.

This chapter studies algorithmic strategies that respond to this tension. Approximation algorithms provide provable bounds on solution quality. Parameterized algorithms identify a small structural parameter that controls exponential effort. Local search and metaheuristics seek high-quality solutions through controlled exploration. Branch-and-bound combines systematic enumeration with mathematical bounds. Intelligent search uses problem structure, learning and adaptive control to guide computation.

These methods are not interchangeable. Approximation emphasizes worst-case guarantees; parameterized complexity emphasizes dependence on structure; exact exponential methods emphasize pruning; heuristics emphasize practical solution quality. Advanced algorithm design requires selecting, combining and evaluating these perspectives rather than treating any one method as universally superior.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Explain why approximation, parameterized and heuristic methods are needed for difficult optimization problems.
2. Construct and analyze approximation algorithms using approximation ratios and performance guarantees.
3. Distinguish approximation algorithms, approximation schemes and parameterized algorithms.
4. Formulate fixed-parameter tractable algorithms and reason about kernelization.
5. Design local-search, branch-and-bound and metaheuristic procedures.
6. Evaluate algorithms using quality, runtime, scalability, robustness and reproducibility.
7. Select an appropriate method for an AI/ML or operations-optimization application.

1. Computational Difficulty and the Design Space

An optimization problem can be represented by a set of feasible solutions F and an objective function f. For a minimization problem, the goal is to find x ∈ F such that f(x) is as small as possible. For a maximization problem, f(x*) is as large as possible. The feasible set may be defined by constraints, logical conditions, graph structure or a learned predictive model.

A polynomial-time exact algorithm is generally preferred, but it may be unavailable for NP-hard problems. The practical design space then includes:

• sacrificing optimality while retaining a theorem about solution quality;
• exploiting a small parameter such as solution size or treewidth;
• enumerating intelligently while pruning impossible or inferior branches;
• searching promising neighborhoods rather than the entire solution space;
• combining several methods in a hybrid algorithm.

The relevant performance dimensions are not only runtime and objective value. A professional evaluation should also consider memory, parallelizability, sensitivity to input order, stability across random seeds, constraint violations, explainability and the cost of obtaining a feasible solution.

2. Approximation Algorithms

2.1 Approximation ratio

Let OPT(I) denote the optimal objective value for instance I, and let A(I) be the value returned by algorithm A. For a minimization problem, A is a ρ-approximation if

For a maximization problem, A is a ρ-approximation if

The ratio is measured against the optimum, not against another heuristic. A ratio of 1 is exact; larger values are weaker for minimization, while a ratio closer to 1 is stronger for both conventions above.

An approximation guarantee is usually worst-case. It does not state that every practical instance will be close to the bound, nor that the algorithm is faster than every competing method. It states that the returned solution cannot be arbitrarily bad relative to optimum under the stated assumptions.

2.2 Greedy design and charging arguments

A common construction pattern is to make a locally attractive choice and then prove its global quality by charging the algorithm's cost to an optimal solution. For example, consider the metric Travelling Salesperson Problem (metric TSP), where distances satisfy non-negativity, symmetry and the triangle inequality.

A minimum spanning tree (MST) has cost at most OPT because removing one edge from an optimal tour produces a spanning tree. Doubling every MST edge creates an Eulerian multigraph of cost at most 2OPT. An Euler tour can be shortcut by skipping already visited vertices; the triangle inequality ensures that shortcutting does not increase cost. Therefore, preorder traversal of a doubled MST yields a tour of cost at most 2OPT.

The proof illustrates a general pattern:

1. construct a lower-bound object, here an MST;
2. transform it into a feasible structure;
3. bound the transformation cost;
4. use structural assumptions, here the triangle inequality, to simplify it safely.

Without the triangle inequality, shortcutting can increase cost arbitrarily, so this guarantee does not apply to general TSP.

2.3 Set Cover and logarithmic guarantees

In Set Cover, a universe U of n elements is given together with subsets S₁, S₂, …, S_m. The task is to select as few subsets as possible whose union is U. The greedy algorithm repeatedly selects the set covering the largest number of currently uncovered elements.

Its approximation ratio is at most 1 + ln n, where ln is the natural logarithm. More precisely, the classical harmonic-number bound is H_n = 1 + 1/2 + ⋯ + 1/n ≤ 1 + ln n. This guarantee is meaningful even though the ratio grows slowly with n. It also reflects a deeper limitation: under standard complexity assumptions, Set Cover cannot generally be approximated substantially better than logarithmic order.

The greedy rule can be extended to weighted Set Cover by selecting the set with the best ratio of cost to newly covered elements. The proof uses a charging argument in which each newly covered element receives a share of the selected set's cost.

2.4 Approximation schemes

An approximation scheme accepts an accuracy parameter ε > 0. A polynomial-time approximation scheme (PTAS) for a minimization problem produces a solution satisfying

for every fixed ε > 0, with polynomial runtime in the input size for that fixed ε. The degree of the polynomial may depend on 1/ε. A fully polynomial-time approximation scheme (FPTAS) is stronger: runtime is polynomial in both input size and 1/ε.

For example, the 0/1 Knapsack problem has an FPTAS based on scaling item values. If item values are nonnegative integers v_i and the largest value is V_max, values can be rounded or scaled so that the dynamic program becomes smaller. The resulting solution can be made within a factor 1 − ε of optimum for maximization, with runtime polynomial in n and 1/ε. The exact scaling details must account for the chosen rounding convention; careless scaling can invalidate the guarantee.

PTAS and FPTAS are different from fixed-parameter tractability. In a scheme, ε controls accuracy and computational cost. In parameterized complexity, a parameter k describes structural difficulty.

3. Parameterized Algorithms

3.1 The parameterized viewpoint

A parameterized problem has input size n and parameter k. An algorithm is fixed-parameter tractable (FPT) if its runtime has the form

where f is any computable function, c is a constant independent of k and n, and the polynomial factor is independent of k. Exponential dependence on a small k may be acceptable; exponential dependence on n usually is not.

For Vertex Cover, k is the desired cover size. The decision problem asks whether a graph G=(V,E) has a vertex cover of size at most k. A simple branching algorithm selects an edge (u,v). Any cover must contain u or v, so the algorithm branches on these two choices and reduces k by one in each branch. Its recurrence is

which gives T(k)=O(2^k · n) under a straightforward implementation. The method is practical when k is small even if the graph itself is large.

3.2 Kernelization

Kernelization preprocesses an instance in polynomial time to produce an equivalent instance whose size is bounded by a function of k. The reduced instance is called a kernel. Equivalence means that the original instance is a yes-instance exactly when the reduced instance is a yes-instance, and a solution can usually be reconstructed.

For Vertex Cover, if a vertex has degree greater than k, every cover of size at most k must include that vertex: otherwise all its neighbors would need to be selected, requiring more than k vertices. Selecting that vertex and reducing k is therefore safe. Other reduction rules remove isolated vertices and simplify forced choices.

A problem is FPT if and only if it admits a kernelization procedure under standard parameterized-complexity formulations. In practice, kernelization is valuable even when a theoretical kernel is not the main algorithm, because preprocessing reduces memory, branching and feature dimensionality.

3.3 Parameter choice and structural insight

A poor parameter can make an FPT algorithm unusable. Common parameters include solution size, treewidth, feedback-vertex-set size, number of machine types, maximum degree and number of exceptional constraints. A useful parameter should be:

• small on the intended application distribution;
• computable or estimable efficiently;
• structurally related to the source of difficulty;
• meaningful to stakeholders.

Parameterized analysis can also reveal that a problem is fixed-parameter tractable for one parameter but W[1]-hard for another. Such results guide algorithm selection and prevent unjustified claims that “small parameter” alone guarantees tractability.

4. Branch-and-Bound

Branch-and-bound is an exact search framework. It recursively partitions the feasible region into subproblems, computes an upper or lower bound for each subproblem, and prunes a subproblem when it cannot improve the incumbent solution.

For a maximization problem, let UB(P) be an upper bound on the best value obtainable in subproblem P. If the incumbent value is z, then P can be discarded when UB(P) ≤ z. For minimization, a lower bound LB(P) permits pruning when LB(P) ≥ z. Correct pruning requires valid bounds; an optimistic upper bound for maximization or optimistic lower bound for minimization must never exclude a potentially optimal solution.

A generic maximization scheme is:

1. obtain a feasible incumbent, often through a heuristic;
2. choose an unresolved subproblem;
3. compute its bound;
4. prune if the bound cannot beat the incumbent;
5. otherwise branch into smaller subproblems;
6. update the incumbent whenever a better feasible solution is found.

Branching strategy affects runtime dramatically. Good rules often branch on a variable with high constraint impact, while good node ordering explores promising branches first. A strong incumbent increases pruning, and a strong bound reduces the number of surviving nodes. Integer programming solvers implement this idea through branch-and-bound, cutting planes, presolve and increasingly sophisticated branching rules.

5. Local Search

Local search begins with a feasible solution and repeatedly applies an improving move from a defined neighborhood. If N(x) is the neighborhood of solution x, a local optimum for maximization satisfies

The neighborhood is part of the algorithm's model of “nearby.” In TSP, a 2-opt move removes two tour edges and reconnects the paths in the alternative way. In scheduling, a move may swap two jobs or move one job to another machine. In clustering, a move may reassign one observation or exchange representatives.

First-improvement accepts the first improving neighbor found; best-improvement evaluates all available moves and selects the best. First-improvement may be faster per iteration, while best-improvement can reduce the number of iterations. Neither dominates universally.

Local optima, plateaus and cycling are central difficulties. Common responses include random restarts, allowing non-improving moves, changing neighborhoods and maintaining tabu restrictions. A neighborhood must preserve feasibility or provide a principled repair mechanism; otherwise objective improvements may be meaningless because constraints are violated.

6. Metaheuristics and Intelligent Search

A metaheuristic is a general strategy for guiding heuristic search across problem instances. It normally contains a representation, an objective or fitness function, a move or variation operator, an acceptance rule and a termination condition.

Simulated annealing

Simulated annealing sometimes accepts a worse move to escape local optima. For a minimization problem, a move with objective increase Δ > 0 may be accepted with probability

where T > 0 is the current temperature. A random number r uniformly distributed on [0,1] is generated, and the move is accepted if r ≤ p. As T decreases according to a cooling schedule, the search becomes less exploratory. The formula assumes a consistent objective scale; if costs are extremely large or differently normalized, the temperature schedule must be adjusted.

Tabu search

Tabu search records recently performed moves or solution attributes in a tabu list. A tabu move is temporarily forbidden unless an aspiration criterion applies, such as producing a solution better than the best known solution. Tabu tenure controls memory length. Short tenure may permit cycling; excessive tenure can block useful regions.

Evolutionary algorithms

Evolutionary algorithms maintain a population of candidate solutions. Selection favors high fitness, while crossover and mutation generate new candidates. Their effectiveness depends strongly on representation. A permutation representation is appropriate for tours, whereas a binary representation may be appropriate for feature selection. Infeasible offspring require repair, penalty functions or constraint-aware operators.

Ant colony and swarm methods

Ant colony optimization constructs solutions using pheromone trails and heuristic desirability. Pheromone evaporation prevents unlimited accumulation of early choices. Particle swarm optimization represents candidates as particles whose positions are influenced by personal and collective best positions; it is naturally suited to continuous spaces but requires careful handling of constraints and discrete decisions.

Learning-guided search

Modern intelligent search may use machine learning to predict promising branches, select neighborhoods, estimate bounds or configure solver parameters. A learned policy should guide, not silently replace, correctness-critical components unless its failure modes are formally controlled. In exact optimization, a learned branching score can be safe if it changes only search order. A learned bound is unsafe unless it is certified as valid or used only as a heuristic incumbent estimator.

7. Worked Example: Branch-and-Bound for 0/1 Knapsack

Suppose a knapsack has capacity 10 and items:

Each item is either selected or rejected. The objective is to maximize total value subject to total weight ≤ 10. A fractional-knapsack relaxation provides an upper bound: items may be fractionally included after the current decisions.

A feasible solution selecting A and B has weight 9 and value 44, so the incumbent is 44. Consider the branch excluding A. Items B, C and D can all be selected: weight 9 and value 39, so this branch cannot improve the incumbent.

For the branch including A, the residual capacity is 4. Selecting C gives weight 10 and value 46, improving the incumbent to 46. The alternative B and D has weight 5 and value 23 in the residual problem, giving total value 53 and weight 11, which is infeasible; B alone gives 44, and C alone gives 46. Thus A+C is a best solution among these combinations with value 46. A fractional bound for a remaining subproblem can prune it if it is no greater than 46. This small example demonstrates the interaction among feasible incumbents, relaxations and pruning; larger instances require careful node ordering and efficient bound computation.

8. Applied Case: AI-Assisted Delivery Routing

Background

Consider a regional delivery company serving several thousand daily orders. Each vehicle has a capacity, driver-hour limit and delivery time windows. Travel times vary with traffic, and some customers require priority service. The resulting vehicle-routing problem is a constrained combinatorial optimization problem.

Problem

An exact mixed-integer formulation can become too slow during morning planning, while a purely greedy route may produce excessive travel and late deliveries. The company needs high-quality routes within ten minutes and must retain operational feasibility.

Analysis and approach

The system uses a hybrid architecture. A constructive heuristic first creates feasible routes using savings-based insertion and time-window checks. Local search then applies relocate, swap and 2-opt* moves between routes. A tabu mechanism prevents immediate cycling. An exact solver is applied to difficult geographic clusters, using the heuristic solution as an incumbent. A learned model predicts which neighborhood is most promising from features such as route slack, stop density and historical improvement rate.

The learned model changes move ordering but does not certify feasibility or optimality. Every accepted route is checked by a deterministic constraint validator. On selected clusters, branch-and-bound supplies lower bounds, allowing the company to report an optimality gap when the search terminates early. For a minimization problem, if a feasible solution has cost z and a valid lower bound is L, the relative gap can be reported as

when L > 0. This quantity is meaningful only when the bound and objective use the same cost definition.

Outcome

The hybrid approach produces feasible plans within the planning deadline, while exact search provides certificates on smaller subproblems. Operational staff can inspect routes and override assignments. The principal benefit is not merely a lower travel distance; it is a controlled balance among cost, service reliability, runtime and explainability.

Learning points

1. Feasibility validation must be independent of a learned heuristic.
2. Good incumbents improve exact search through stronger pruning.
3. Decomposition can expose small parameters or manageable clusters.
4. Report bounds, runtime and failure cases rather than only average objective values.

9. Evaluation, Limitations and Governance

Approximation guarantees are worst-case and may be loose. Heuristics often perform well empirically but lack universal guarantees. Metaheuristics can be sensitive to random seeds, parameter settings and stopping rules. Branch-and-bound can experience exponential memory or runtime. Parameterized methods may be excellent only when the chosen parameter is genuinely small.

A sound experimental protocol should use representative benchmark families, separate training and test instances when learning is involved, report distributions rather than only means, include baselines, disclose hardware and stopping criteria, and perform ablation studies. For stochastic algorithms, confidence intervals or repeated-run summaries are preferable to a single best run.

In operational AI, optimization objectives can encode social priorities. A routing objective that minimizes distance alone may disadvantage remote communities or shift difficult work to particular drivers. Constraints involving fairness, safety, accessibility, privacy and labor regulation should be explicit. Sensitive historical data used to learn branching or dispatch policies may reproduce institutional bias. Human override, audit logs and rollback procedures are essential in high-impact settings.

10. Best-Practice Design Workflow

1. Define the objective, constraints and acceptable violations precisely.
2. Determine whether an exact polynomial algorithm exists before using a heuristic.
3. Seek relaxations, lower bounds, structural parameters and decomposition opportunities.
4. Build a simple feasible baseline before adding sophisticated search.
5. Match representation and neighborhoods to the problem structure.
6. Use approximation algorithms when a guarantee is valuable and available.
7. Use branch-and-bound with strong valid bounds and good incumbents.
8. Tune stochastic methods on validation instances, not on the final test set.
9. Combine methods only when interfaces preserve feasibility and interpretability.
10. Report quality, runtime, robustness, gaps and limitations transparently.

Chapter Summary

Difficult optimization problems require a portfolio of algorithmic ideas. Approximation algorithms trade exactness for provable quality, with ratios, PTASs and FPTASs offering different forms of control. Parameterized algorithms exploit a small structural parameter, while kernelization reduces instances before expensive computation. Branch-and-bound obtains exact answers through valid bounds, branching and pruning. Local search explores neighborhoods; simulated annealing, tabu search, evolutionary methods and swarm approaches provide broader exploration. Learning can improve ordering and configuration, but correctness-critical feasibility and bounds require independent validation.

The central design principle is alignment: the guarantee, parameter, neighborhood, bound or learned signal must match the structure and risks of the application. Evaluation must include more than objective value, incorporating runtime, reliability, reproducibility, fairness and governance.

Key Terms

Approximation ratio: Worst-case comparison between an algorithm's solution and the optimum.

Approximation scheme: Algorithm whose accuracy is controlled by parameter ε.

Branch-and-bound: Exact search using branching and valid bounds to prune subproblems.

Cooling schedule: Rule controlling temperature reduction in simulated annealing.

FPT: Fixed-parameter tractable runtime of the form f(k)·n^c.

Heuristic: Method designed to find good solutions without a universal optimality guarantee.

Incumbent: Best feasible solution currently known during search.

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

Local optimum: Solution with no improving solution in its chosen neighborhood.

Metaheuristic: General strategy for guiding heuristic search.

Neighborhood: Set of solutions reachable by an allowed local move.

Optimality gap: Difference between a feasible objective and a valid bound on the optimum.

Parameter: Structural quantity controlling the difficult part of a parameterized problem.

PTAS: Polynomial-time approximation scheme for each fixed accuracy value.

Pruning: Discarding a search subproblem that cannot improve the incumbent.

Relaxation: Problem obtained by weakening constraints to derive a bound.

Tabu search: Local search using memory to discourage cycling.

Valid bound: Bound that cannot incorrectly exclude an optimal solution.

Review Questions

Short Answer Questions

1. What is the approximation guarantee for a minimization algorithm returning value A(I) when the optimum is OPT(I)?
2. Define fixed-parameter tractability and identify the role of parameter k.
3. Why is the triangle inequality essential in the MST-based 2-approximation for metric TSP?
4. What is the purpose of an incumbent in branch-and-bound?
5. State one difference between first-improvement and best-improvement local search.

Long Answer Questions

1. Explain approximation ratios, PTASs and FPTASs, and compare the guarantees and runtime implications of each.
2. Derive the branching recurrence for the basic Vertex Cover algorithm and explain why each branch is exhaustive.
3. Describe how bounds, branching order and incumbents interact in branch-and-bound.
4. Compare simulated annealing, tabu search and evolutionary algorithms in terms of exploration, memory and parameter control.
5. Design an evaluation protocol for a stochastic optimization algorithm used in production.

Analytical / Application Questions

1. Design a hybrid approximation and local-search algorithm for a capacitated routing problem. Specify its representation, neighborhood, feasibility mechanism and stopping rule.
2. A minimization solver returns cost 1,250 and a valid lower bound of 1,000. Compute the relative optimality gap and explain what the result does and does not prove.
3. For a graph problem, propose two possible parameters, explain which is likely to support an FPT approach, and justify your choice using the expected structure of real instances.

Multiple Choice Questions with Answers

Question 1

For a minimization problem, which condition defines a ρ-approximation?

A. A(I) ≥ ρ·OPT(I)

B. A(I) ≤ ρ·OPT(I), with ρ ≥ 1

C. A(I) = OPT(I) − ρ

D. A(I) ≤ OPT(I)/ρ, with ρ ≥ 1

Correct Answer: B. A(I) ≤ ρ·OPT(I), with ρ ≥ 1

Question 2

What is the defining runtime form of an FPT algorithm?

A. n^k

B. 2^n·k

C. f(k)·n^c

D. k·log n

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

Question 3

Which assumption enables shortcutting in the MST-based 2-approximation for metric TSP without increasing tour cost?

A. Graph completeness only

B. The triangle inequality

C. All edges having equal weight

D. The graph being acyclic

Correct Answer: B. The triangle inequality

Question 4

In maximization branch-and-bound, when may a subproblem with upper bound UB be pruned?

A. When UB is greater than the incumbent

B. When UB equals zero only

C. When UB is no greater than the incumbent

D. Whenever the subproblem has two branches

Correct Answer: C. When UB is no greater than the incumbent

Question 5

Which statement about a PTAS is correct?

A. Its runtime must be polynomial in n and 1/ε

B. For every fixed ε, it runs in polynomial time in input size

C. It always returns an exact optimum

D. It is defined only for maximization problems

Correct Answer: B. For every fixed ε, it runs in polynomial time in input size

Question 6

In simulated annealing for minimization, what happens to acceptance probability for a fixed worsening Δ > 0 as temperature T decreases?

A. It increases to 1

B. It remains exactly constant

C. It decreases

D. It becomes negative

Correct Answer: C. It decreases

Question 7

What is the main purpose of kernelization?

A. To convert every problem into a polynomial-time problem

B. To produce an equivalent smaller instance bounded by a function of k

C. To remove the objective function

D. To guarantee a 1-approximation

Correct Answer: B. To produce an equivalent smaller instance bounded by a function of k

Question 8

A minimization algorithm returns cost 1250 and a valid lower bound is 1000. What is the relative gap (z−L)/L?

A. 0.025

B. 0.25

C. 1.25

D. 250

Correct Answer: B. 0.25

Question 9

Which feature most directly helps branch-and-bound prune more nodes?

A. A weaker bound

B. A poorer incumbent

C. A stronger valid bound

D. Randomly disabling feasibility checks

Correct Answer: C. A stronger valid bound

Question 10

What is a central risk when a learned model supplies an uncertified bound in an exact optimization algorithm?

A. The search may become deterministic

B. The model may incorrectly prune an optimal solution

C. The input size becomes zero

D. The objective automatically becomes convex

Correct Answer: B. The model may incorrectly prune an optimal solution