Contents
Chandra Chekuri

Approximation Algorithms: Introduction

These are the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 1: Introduction. You can read Chapter 2: Covering problems here.
Course Objectives
  1. To appreciate that not all intractable problems are the same. N P N P NP\mathbf{NP} optimization problems, identical in terms of exact solvability, can appear very different from the approximation point of view. This sheds light on why, in practice, some optimization problems (such as Кnapsack) are easy, while others (like Clique) are extremely difficult.
  2. To learn techniques for design and analysis of approximation algorithms, via some fundamental problems.
  3. To build a toolkit of broadly applicable algorithms/heuristics that can be used to solve a variety of problems.
  4. To understand reductions between optimization problems, and to develop the ability to relate new problems to known ones.
The complexity class P P P\mathbf{P} contains the set of problems that can be solved in polynomial time. From a theoretical viewpoint, this describes the class of tractable problems, that is, problems that can be solved efficiently. The class N P N P NP\mathbf{NP} is the set of problems that can be solved in non-deterministic polynomial time, or equivalently, problems for which a solution can be verified in polynomial time. N P N P NP\mathbf{NP} contains many interesting problems that often arise in practice, but there is good reason to believe P ≠ N P P ≠ N P P!=NP\mathbf{P} \neq \mathbf{N P}. That is, it is unlikely that there exist algorithms to solve NP optimization problems efficiently, and so we often resort to heuristic methods to solve these problems.
Heuristic approaches include backtrack search and its variants, mathematical programming methods, local seach, genetic algorithms, tabu search, simulated annealing etc. Some methods are guaranteed to find an optimal solution, though they may take exponential time; others are guaranteed to run in polynomial time, though they may not return a (optimal) solution. Approximation algorithms are (typically) polynomial time heuristics that do not always find an optimal solution but they are distinguished from general heuristics in providing guarantees on the quality of the solution they output.
Approximation Ratio: To give a guarantee on solution quality, one must first define what we mean by the quality of a solution. We discuss this more carefully later. For now, note that each instance of an optimization problem has a set of feasible solutions. The optimization problems we consider have an objective function which assigns a (real/rational) number/value to each feasible solution of each instance I I II. The goal is to find a feasible solution with minimum objective function value or maximum objective function value. The former problems are minimization problems and the latter are maximization problems.
For each instance I I II of a problem, let OPT ⁡ ( I ) OPT ⁡ ( I ) OPT(I)\operatorname{OPT}(I) denote the value of an optimal solution to instance I I II. We say that an algorithm A A A\mathcal{A} is an α α alpha\alpha-approximation algorithm for a problem if, for every instance I I II, the value of the feasible solution returned by A A A\mathcal{A} is within a (multiplicative) factor of α α alpha\alpha of OPT ⁡ ( I ) OPT ⁡ ( I ) OPT(I)\operatorname{OPT}(I). Equivalently, we say that A A A\mathcal{A} is an approximation algorithm with approximation ratio α α alpha\alpha. For a minimization problem we would have α ≥ 1 α ≥ 1 alpha >= 1\alpha \geq 1 and for a maximization problem we would have α ≤ 1 α ≤ 1 alpha <= 1\alpha \leq 1. However, it is not uncommon to find in the literature a different convention for maximization problems where one says that A A A\mathcal{A} is an α α alpha\alpha-approximation algorithm if the value of the feasible solution returned by A A A\mathcal{A} is at least 1 α ⋅ OPT ⁡ ( I ) 1 α ⋅ OPT ⁡ ( I ) (1)/(alpha)*OPT(I)\frac{1}{\alpha} \cdot \operatorname{OPT}(I); the reason for using convention is so that approximation ratios for both minimization and maximization problems will be ≥ 1 ≥ 1 >= 1\geq 1. In this course we will for the most part use the convention that α ≥ 1 α ≥ 1 alpha >= 1\alpha \geq 1 for minimization problems and α ≤ 1 α ≤ 1 alpha <= 1\alpha \leq 1 for maximization problems.
Remarks:
  1. The approximation ratio of an algorithm for a minimization problem is the maximum (or supremum), over all instances of the problem, of the ratio between the values of solution returned by the algorithm and the optimal solution. Thus, it is a bound on the worst-case performance of the algorithm.
  2. The approximation ratio α α alpha\alpha can depend on the size of the instance I I II, so one should technically write α ( | I | ) α ( | I | ) alpha(|I|)\alpha(|I|).
  3. A natural question is whether the approximation ratio should be defined in an additive sense. For example, an algorithm has an α α alpha\alpha-approximation for a minimization problem if it outputs a feasible solution of value at most OPT ⁡ ( I ) + α OPT ⁡ ( I ) + α OPT(I)+alpha\operatorname{OPT} (I)+\alpha for all I I II. This is a valid definition and is the more relevant one in some settings. However, for many N P N P NP\mathbf{NP} problems it is easy to show that one cannot obtain any interesting additive approximation (unless of course P = N P P = N P P=NPP=NP ) due to scaling issues. We will illustrate this via an example later.
Pros and cons of the approximation approach: Some advantages to the approximation approach include:
  1. It explains why problems can vary considerably in difficulty.
  2. The analysis of problems and problem instances distinguishes easy cases from difficult ones.
  3. The worst-case ratio is robust in many ways. It allows reductions between problems.
  4. Approximation allgorithmic ideas/tools/relaxations are valuable in developing heuristics, including many that are practical and effective.
  5. Quantification of performance via a concrete metric such as the approximation ratio allows for innovation in algorithm design and has led to many new ideas.
As a bonus, many of the ideas are beautiful and sophisticated, and involve connections to other areas of mathematics and computer science.
    Disadvantages include:
  1. The focus on worst-case measures risks ignoring algorithms or heuristics that are practical or perform well on average.
  2. Unlike, for example, integer programming, there is often no incremental/continuous tradeoff between the running time and quality of solution.
  3. Approximation algorithms are often limited to cleanly stated problems.
  4. The framework does not (at least directly) apply to decision problems or those that are inapproximable.
Approximation as a broad lens
The use of approximation algorithms is not restricted solely to N P N P NP\mathbf{NP}-Hard optimization problems. In general, ideas from approximation can be used to solve many problems where finding an exact solution would require too much of any resource.
A resource we are often concerned with is time. Solving N P N P NP\mathbf{NP}-Hard problems exactly would (to the best of our knowledge) require exponential time, and so we may want to use approximation algorithms. However, for large data sets, even polynomial running time is sometimes unacceptable. As an example, the best exact algorithm known for the Matching problem in general graphs requires O ( m n ) O ( m n ) O(msqrtn)O(m \sqrt{n}) time; on large graphs, this may be not be practical. In contrast, a simple greedy algorithm takes near-linear time and outputs a matching of cardinality at least 1 / 2 1 / 2 1//21 / 2 that of the maximum matching; moreover there have been randomized sub-linear time algorithms as well.
Another often limited resource is space. In the area of data streams/streaming algorithms, we are often only allowed to read the input in a single pass, and given a small amount of additional storage space. Consider a network switch that wishes to compute statistics about the packets that pass through it. It is easy to exactly compute the average packet length, but one cannot compute the median length exactly. Surprisingly, though, many statistics can be approximately computed.
Other resources include programmer time (as for the Matching problem, the exact algorithm may be significantly more complex than one that returns an approximate solution), or communication requirements (for instance, if the computation is occurring across multiple locations).

1.1 Formal Aspects

1.1.1 NP Optimization Problems

In this section, we cover some formal definitions related to approximation algorithms. We start from the definition of optimization problems. A problem is simply an infinite collection of instances. Let Π Π Pi\Pi be an optimization problem. Π Π Pi\Pi can be either a minimization or maximixation problem. Instances I I II of Π Π Pi\Pi are a subset of Σ ∗ Σ ∗ Sigma^(**)\Sigma^{*} where Σ Σ Sigma\Sigma is a finite encoding alphabet. For each instance I I II there is a set of feasible solutions S ( I ) S ( I ) S(I)\mathcal{S}(I). We restrict our attention to real/rational-valued optimization problems; in these problems each feasible solution S ∈ S ( I ) S ∈ S ( I ) S inS(I)S \in \mathcal{S}(I) has a value val ⁡ ( S , I ) val ⁡ ( S , I ) val(S,I)\operatorname{val} (S, I). For a minimization problem Π Π Pi\Pi the goal is, given I I II, find O P T ( I ) = min S ∈ S ( I ) val ⁡ ( S , I ) O P T ( I ) = min S ∈ S ( I )   val ⁡ ( S , I ) OPT(I)=min_(S inS(I))val(S,I)\mathrm{OPT}(I)=\min _{S \in \mathcal{S}(I)} \operatorname{val} (S, I).
Now let us formally define NP NP NP\operatorname{NP} optimization ( NPO NPO NPO\operatorname{NPO}) which is the class of optimization problems corresponding to N P N P NPN P.
Definition 1.1. Π Π Pi\Pi is in N P O N P O NPONPO if
  • Given x ∈ Σ ∗ x ∈ Σ ∗ x inSigma^(**)x \in \Sigma^{*}, there is a polynomial-time algorithm that decide if x x xx is a valid instance of Π Π Pi\Pi*. That is, we can efficiently check if the input string is well-formed. This is a basic requirement that is often not spelled out.
  • For each I I II, and S ∈ S ( I ) , | S | ≤ poly ⁡ ( | I | ) S ∈ S ( I ) , | S | ≤ poly ⁡ ( | I | ) S inS(I),|S| <= poly(|I|)S \in \mathcal{S}(I),|S| \leq \operatorname{poly}(|I|). That is, the solution are of size polynomial in the input size.
  • There exists a poly-time decision procedure that for each I I II and S ∈ Σ ∗ S ∈ Σ ∗ S inSigma^(**)S \in \Sigma^{*}, decides if S ∈ S ( I ) S ∈ S ( I ) S inS(I)S \in \mathcal{S}(I). This is the key property of NP; we should be able to verify solutions efficiently.
  • val ⁡ ( I , S ) val ⁡ ( I , S ) val(I,S)\operatorname{val} (I, S) is a polynomial-time computable function.
We observe that for a minimization NPO NPO NPO\operatorname{NPO} problem Π Π Pi\Pi, there is a associated natural decision problem L ( Π ) = { ( I , B ) : OPT ⁡ ( I ) ≤ B } L ( Π ) = { ( I , B ) : OPT ⁡ ( I ) ≤ B } L(Pi)={(I,B):OPT(I) <= B}L(\Pi)=\{(I, B): \operatorname{OPT}(I) \leq B\} which is the following: given instance I I II of Π Π Pi\Pi and a number B B BB, is the optimal value on I I II at most B B BB? For maximization problem Π Π Pi\Pi we reverse the inequality in the definition.
Lemma 1.1. L ( Π ) L ( Π ) L(Pi)L(\Pi) is in N P N P NPNP if Π Π Pi\Pi is in N P O N P O NPONPO.

1.1.2 Relative Approximation

When Π Π Pi\Pi is a minimization problem, recall that we say an approximation algorithm A A A\mathcal{A} is said to have approximation ratio α α alpha\alpha iff
  • A A A\mathcal{A} is a polynomial time algorithm
  • for all instance I I II of Π , A Π , A Pi,A\Pi, \mathcal{A} produces a feasible solution A ( I ) A ( I ) A(I)\mathcal{A}(I) s.t. val ⁡ ( A ( I ) , I ) ≤ α val ⁡ ( O P T ( I ) , I ) val ⁡ ( A ( I ) , I ) ≤ α val ⁡ ( O P T ( I ) , I ) val(A(I),I) <= alpha val(OPT(I),I)\operatorname{val}(\mathcal{A}(I), I) \leq \alpha \operatorname{val} (\mathrm{OPT}(I), I). (Note that α ≥ 1 α ≥ 1 alpha >= 1\alpha \geq 1.)
Approximation algorithms for maximization problems are defined similarly. An approximation algorithm A A A\mathcal{A} is said to have approximation ratio α α alpha\alpha iff
  • A A A\mathcal{A} is a polynomial time algorithm
  • for all instance I I II of Π , A Π , A Pi,A\Pi, \mathcal{A} produces a feasible solution A ( I ) A ( I ) A(I)\mathcal{A}(I) s.t. val ⁡ ( A ( I ) , I ) ≥ val ⁡ ( A ( I ) , I ) ≥ val(A(I),I) >=\operatorname{val}(\mathcal{A}(I), I) \geq α val ⁡ ( OPT ⁡ ( I ) , I ) α val ⁡ ( OPT ⁡ ( I ) , I ) alpha val(OPT(I),I)\alpha \operatorname{val}(\operatorname{OPT}(I), I). (Note that α ≤ 1 α ≤ 1 alpha <= 1\alpha \leq 1.)
For maximization problems, it is also common to see use 1 / α 1 / α 1//alpha1 / \alpha (which must be ≥ 1 ≥ 1 >= 1\geq 1 ) as approximation ratio.

1.1.3 Additive Approximation

Note that all the definitions above are about relative approximations; one could also define additive approximations. A A A\mathcal{A} is said to be an α α alpha\alpha-additive approximation algorithm, if for all I , val ⁡ ( A ( I ) ) ≤ OPT ⁡ ( I ) + α I , val ⁡ ( A ( I ) ) ≤ OPT ⁡ ( I ) + α I,val(A(I)) <= OPT(I)+alphaI, \operatorname{val}(\mathcal{A}(I)) \leq \operatorname{OPT} (I)+\alpha. Most NPO NPO NPO\operatorname{NPO} problems, however, do not allow any additive approximation ratio because OPT ⁡ ( I ) OPT ⁡ ( I ) OPT(I)\operatorname{OPT}(I) has a scaling property.
To illustrate the scaling property, let us consider Metric-TSP. Given an instance I I II, let I β I β I_(beta)I_{\beta} denote the instance obtained by increasing all edge costs by a factor of β β beta\beta. It is easy to observe that for each S ∈ S ( I ) = S ( I β ) val ⁡ ( S , I β ) = β val ⁡ ( S , I β ) S ∈ S ( I ) = S I β val ⁡ S , I β = β val ⁡ S , I β S inS(I)=S(I_(beta))val(S,I_(beta))=beta val(S,I_(beta))S \in \mathcal{S}(I)=\mathcal{S}\left(I_{\beta}\right) \operatorname{val}\left(S, I_{\beta}\right)=\beta \operatorname{val}\left(S, I_{\beta}\right) and OPT ⁡ ( I β ) = β OPT ⁡ ( I ) OPT ⁡ I β = β OPT ⁡ ( I ) OPT(I_(beta))=beta OPT(I)\operatorname{OPT}\left(I_{\beta}\right)=\beta \operatorname{OPT}(I). Intuitively, scaling edge by a factor of β β beta\beta scales the value by the same factor β β beta\beta. Thus by choosing β β beta\beta sufficiently large, we can essentially make the additive approximation(or error) negligible.
Lemma 1.2. Metric-TSP does not admit an α α alpha\alpha additive approximation algorithm for any polynomial-time computable α α alpha\alpha unless P = N P P = N P P=NPP=N P.
Proof. For simplicity, suppose every edge has integer cost. For the sake of contradiction, suppose there exists an additive α α alpha\alpha approximation A A A\mathcal{A} for Metric-TSP. Given I I II, we run the algorithm on I β I β I_(beta)I_{\beta} and let S S SS be the solution, where β = 2 α β = 2 α beta=2alpha\beta=2 \alpha. We claim that S S SS is the optimal solution for I I II. We have val ⁡ ( S , I ) = val ⁡ ( S , I β ) / β ≤ val ⁡ ( S , I ) = val ⁡ S , I β / β ≤ val(S,I)=val(S,I_(beta))//beta <=\operatorname{val}(S, I)=\operatorname{val}\left(S, I_{\beta}\right) / \beta \leq OPT ⁡ ( I β ) / β + α / β = OPT ⁡ ( I ) + 1 / 2 OPT ⁡ I β / β + α / β = OPT ⁡ ( I ) + 1 / 2 OPT(I_(beta))//beta+alpha//beta=OPT(I)+1//2\operatorname{OPT}\left(I_{\beta}\right) / \beta+\alpha / \beta=\operatorname{OPT}(I)+1 / 2, as A A A\mathcal{A} is α α alpha\alpha-additive approximation. Thus we conclude that OPT ⁡ ( I ) = val ⁡ ( S , I ) OPT ⁡ ( I ) = val ⁡ ( S , I ) OPT(I)=val(S,I)\operatorname{OPT} (I)=\operatorname{val}(S, I), since OPT ⁡ ( I ) ≤ val ⁡ ( S , I ) OPT ⁡ ( I ) ≤ val ⁡ ( S , I ) OPT(I) <= val(S,I)\operatorname{OPT} (I) \leq \operatorname{val}(S, I), and OPT ⁡ ( I ) , val ⁡ ( S , I ) OPT ⁡ ( I ) , val ⁡ ( S , I ) OPT(I),val(S,I)\operatorname{OPT}(I),\operatorname{val}(S, I) are integers. This is impossible unless P = N P P = N P P=NPP=N P.
Now let us consider two problems which allow additive approximations. In the Planar Graph Coloring, we are given a planar graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E). We are asked to color all vertices of the given graph G G GG such that for any v w ∈ E , v v w ∈ E , v vw in E,vv w \in E, v and w w ww have different colors. The goal is to minimize the number of different colors. It is known that to decide if a planar graph admits 3 3 33-coloring is NP NP NP\operatorname{NP}-complete [1], while one can always color any planar graph G G GG with using 4 4 44 colors (this is the famous 4 4 44-color theorem) [2] [3]. Further, one can efficiently check whether a graph is 2 2 22-colorable (that is, if it is bipartite). Thus, the following algorithm is a 1 1 11-additive approximation for Planar Graph Coloring: If the graph is bipartite, color it with 2 2 22 colors; otherwise, color with 4 4 44 colors.
As a second example, consider the Edge Coloring Problem, in which we are asked to color edges of a given graph G G GG with the minimum number of different colors so that no two adjacent edges have different colors. By Vizing's theorem[4], we know that one can color edges with either Δ ( G ) Δ ( G ) Delta(G)\Delta(G) or Δ ( G ) + 1 Δ ( G ) + 1 Delta(G)+1\Delta(G)+1 different colors, where Δ ( G ) Δ ( G ) Delta(G)\Delta(G) is the maximum degree of G G GG. Since Δ ( G ) Δ ( G ) Delta(G)\Delta(G) is a trivial lower bound on the minimum number, we can say that the Edge Coloring Problem allows a 1 1 11-additive approximation. Note that the problem of deciding whether a given graph can be edge colored with Δ ( G ) Δ ( G ) Delta(G)\Delta(G) colors is NP-complete[5].

1.1.4 Hardness of Approximation

Now we move to hardness of approximation.
Definition 1.2 (Approximability Threshold). Given a minimization optimization problem Π Π Pi\Pi, it is said that Π Π Pi\Pi has an approximation threshold α ∗ ( Π ) α ∗ ( Π ) alpha^(**)(Pi)\alpha^{*}(\Pi), if for any ϵ > 0 ϵ > 0 epsilon > 0\epsilon>0, Π Π Pi\Pi admits a α ∗ ( Π ) + ϵ α ∗ ( Π ) + ϵ alpha^(**)(Pi)+epsilon\alpha^{*}(\Pi)+\epsilon approximation but if it admits a α ∗ ( Π ) − ϵ α ∗ ( Π ) − ϵ alpha^(**)(Pi)-epsilon\alpha^{*}(\Pi)-\epsilon approximation then P = N P P = N P P=NPP=N P.
If α ∗ ( Π ) = 1 α ∗ ( Π ) = 1 alpha^(**)(Pi)=1\alpha^{*}(\Pi)=1, it implies that Π Π Pi\Pi is solvable in polynomial time. Many NPO NPO NPO\operatorname{NPO} problems Π Π Pi\Pi are known to have α ∗ ( Π ) > 1 α ∗ ( Π ) > 1 alpha^(**)(Pi) > 1\alpha^{*}(\Pi)>1 assuming that P ≠ N P P ≠ N P P!=NPP \neq N P. We can say that approximation algorithms try to decrease the upper bound on α ∗ ( Π ) α ∗ ( Π ) alpha^(**)(Pi)\alpha^{*}(\Pi), while hardness of approximation attempts to increase lower bounds on α ∗ ( Π ) α ∗ ( Π ) alpha^(**)(Pi)\alpha^{*}(\Pi).
To prove hardness results on NPO NPO NPO\operatorname{NPO} problems in terms of approximation, there are largely two approaches; a direct way by reduction from NP NP NP\operatorname{NP}-complete problems and an indirect way via gap reductions. Here let us take a quick look at an example using a reduction from an NP NP NP\operatorname{NP}-complete problem.
In the (metric) k k kk-center problem, we are given an undirected graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and an integer k k kk. We are asked to choose a subset of k k kk vertices from V V VV called centers. The goal is to minimize the maximum distance to a center, i.e. min S ⊆ V , | S | = k max v ∈ V dist G ⁡ ( v , S ) min S ⊆ V , | S | = k   max v ∈ V   dist G ⁡ ( v , S ) min_(S sube V,|S|=k)max_(v in V)dist_(G)(v,S)\min _{S \subseteq V,|S|=k} \max _{v \in V} \operatorname{dist}_{G}(v, S), where dist G ⁡ ( v , S ) = min u ∈ S dist G ⁡ ( u , v ) dist G ⁡ ( v , S ) = min u ∈ S   dist G ⁡ ( u , v ) dist_(G)(v,S)=min_(u in S)dist_(G)(u,v)\operatorname{dist}_{G}(v, S)=\min _{u \in S} \operatorname{dist}_{G}(u, v).
The k k kk-center problem has approximation threshold 2 2 22, since there are a few 2 2 22-approximation algorithms for k k kk-center and there is no 2 − ϵ 2 − ϵ 2-epsilon2-\epsilon approximation algorithm for any ϵ > 0 ϵ > 0 epsilon > 0\epsilon>0 unless P = N P P = N P P=NPP=N P. We can prove the inapproximability using a reduction from the decision version of Dominating Set: Given an undirected graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and an integer k k kk, does G G GG have a dominating set of size at most k k kk? A set S ⊆ V S ⊆ V S sube VS \subseteq V is said to be a dominating set in G G GG if for all v ∈ V , v ∈ S v ∈ V , v ∈ S v in V,v in Sv \in V, v \in S or v v vv is adjacent to some u u uu in S S SS. Dominating Set is known to be NP NP NP\operatorname{NP}-complete.
Theorem 1.3 ([6]). Unless P = N P P = N P P=NPP=N P, there is no 2 − ϵ 2 − ϵ 2-epsilon2-\epsilon approximation for k k kk-center for any fixed ϵ > 0 ϵ > 0 epsilon > 0\epsilon>0.
Proof. Let I I II be an instance of Dominating Set Problem consisting of graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and integer k k kk. We create an instance I ′ I ′ I^(')I^{\prime} of k k kk-center while keeping graph G G GG and k k kk the same. If I I II has a dominating set of size k k kk then OPT ⁡ ( I ′ ) = 1 OPT ⁡ ( I ′ ) = 1 OPT(I^('))=1\operatorname{OPT}(I^{\prime}) =1, since every vertex can be reachable from the Dominating Set by at most one hop. Otherwise, we claim that OPT ⁡ ( I ′ ) ≥ 2 OPT ⁡ I ′ ≥ 2 OPT(I^(')) >= 2\operatorname{OPT}\left(I^{\prime}\right) \geq 2. This is because if OPT ⁡ ( I ′ ) < 2 OPT ⁡ I ′ < 2 OPT(I^(')) < 2\operatorname{OPT}\left(I^{\prime}\right)<2, then every vertex must be within distance 1, which implies the k k kk-center that witnesses OPT ⁡ ( I ′ ) OPT ⁡ I ′ OPT(I^('))\operatorname{OPT}\left(I^{\prime}\right) is a dominating set of I I II. Therefore, the ( 2 − ϵ ) ( 2 − ϵ ) (2-epsilon)(2-\epsilon) approximation for k k kk-center can be used to solve the Dominating Set Problem. This is impossible, unless P = N P P = N P P=NPP=N P.

1.2 Designing Approximation Algorithms

How does one design and more importantly analyze the performance of approximation algorithms? This is a non-trivial task and the main goal of the course is to expose you to basic and advanced techniques as well as central problems. The purpose of this section is to give some high-level insights. We start with how we design polynomial-time algorithms. Note that approximation makes sense mainly in the setting where one can find a feasible solution relatively easily but finding an optimum solution is hard. In some cases finding a feasible solution itself may involve some non-trivial algorithm, in which case it is useful to properly understand the structural properties that guarantee feasibility, and then build upon it.
Some of the standard techniques we learn in basic and advanced undergraduate algorithms courses are recursion based methods such as divide and conquer, dynamic programming, greedy, local search, combinatorial optimization via duality, and reductions to existing problems. How do we adapt these to the approximation setting? Note that intractability implies that there are no efficient characterizations of the optimum solution value.
Greedy and related techniques are often fairly natural for many problems and simple heuristic algorithms often suggest themselves for many problems. (Note that the algorithms may depend on being able to solve some existing problem efficiently. Thus, knowing a good collection of general poly-time solvable problems is often important.) The main difficulty is in analyzing their performance. The key challenge here is to identify appropriate lower bounds on the optimal value (assuming that the problem is a minimization problem) or upper bounds on the optimal value (assuming that the problem is a maximization problem). These bounds allow one to compare the output of the algorithm and prove an approximation bound. In designing poly-time algorithms we often prove that greedy algorithms do not work. We typically do this via examples. This skill is also useful in proving that some candidate algorithm does not give a good approximation. Often the bad examples lead one to a new algorithm.
How does one come up with lower or upper bounds on the optimum value? This depends on the problem at hand and knowing some background and related problems. However, one would like to find some automatic ways of obtaining bounds. This is often provided via linear programming relaxations and more advanced convex programming methods including semi-definite programming, lift-and-project hierarchies etc. The basic idea is quite simple. Since integer linear programming is NP NP NP\operatorname{NP}-Complete one can formulate most discrete optimization problems easily and "naturally" as an integer program. Note that there may be many different ways of expressing a given problem as an integer program. Of course we cannot solve the integer program but we can solve the linear-programming relaxation which is obtained by removing the integrality constraints on the variables. Thus, for each instance I I II of a given problem we can obtain an LP LP LP\operatorname{LP} relaxation L P ( I ) L P ( I ) LP(I)L P(I) which we typically can be solve in polynomial-time. This automatically gives a bound on the optimum value since it is a relaxation. How good is this bound? It depends on the problem, of course, and also the specific LP LP LP\operatorname{LP} relaxation. How do we obtain a feasible solution that is close to the bound given by the LP LP LP\operatorname{LP} relaxation. The main technique here is to round the fractional solution x x xx to an integer feasible solution x ′ x ′ x^(')x^{\prime} such that x ′ ′ x ′ ′ x^('')x^{\prime \prime}s value is close to that of x x xx. There are several non-trivial rounding techniques that have been developed over the years that we will explore in the course. We should note that in several cases one can analyze combinatorial algorithms via LP LP LP\operatorname{LP} relaxations even though the LP LP LP\operatorname{LP} relaxation does not play any direct role in the algorithm itself. Finally, there is the question of which LP LP LP\operatorname{LP} relaxation to use. Often it is required to "strengthen" an LP LP LP\operatorname{LP} relaxation via addition of constraints to provide better bounds. There are some automatic ways to strengthen any LP LP LP\operatorname{LP} and often one also needs problem specific ideas.
Local search is another powerful technique and the analysis here is not obvious. One needs to relate the value of a local optimum to the value of a global optimum via various exchange properties which define the local search heuristic. For a formal analysis it is necessary to have a good understanding of the problem structure.
Finally, dynamic programming plays a key role in the following way. Its main use is in solving to optimality a restricted version of the given problem or a subroutine that is useful as a building block. How does one obtain a restricted version? This is often done by some clever proprocessing of a given instance.
Reductions play a very important role in both designing approximation algorithms and in proving inapproximability results. Often reductions serve as a starting point in developing a simple and crude heuristic that allows one to understand the structure of a problem which then can lead to further improvements.
Discrete optimization problems are brittle–changing the problem a little can lead to substantial changes in the complexity and approximability. Nevertheless it is useful to understand problems and their structure in broad categories so that existing results can be leveraged quickly and robustly. Thus, some of the emphasis in the course will be on classifying problems and how various parameters influence the approximability.
  1. Larry Stockmeyer. “Planar 3-colorability is Polynomial Complete”. In: SIGACT News 5.3 (July 1973), pp. 19–25. issn: 0163-5700. doi: 10.1145/ 1008293.1008294. url: http://doi.acm.org/10.1145/1008293.1008294. ↩︎
  2. Kenneth Appel, Wolfgang Haken, et al. “Every planar map is four colorable. Part I: Discharging”. In: Illinois Journal of Mathematics 21.3 (1977), pp. 429–490. ↩︎
  3. Robin Thomas. “An update on the four-color theorem”. In: Notices of the AMS 45.7 (1998), pp. 848–859. ↩︎
  4. Douglas Brent West et al. Introduction to graph theory. Vol. 2. Prentice hall Upper Saddle River, 2001. ↩︎
  5. Ian Holyer. “The NP-completeness of edge-coloring”. In: SIAM Journal on computing 10.4 (1981), pp. 718–720. ↩︎
  6. Wen-Lian Hsu and George L Nemhauser. “Easy and hard bottleneck location problems”. In: Discrete Applied Mathematics 1.3 (1979), pp. 209– 215. ↩︎

Recommended for you

Emil Junker
Manipulative Attacks in Group Identification
Manipulative Attacks in Group Identification
This review provides an introduction to the group identification problem and gives an overview of the feasibility and computational complexity of manipulative attacks in group identification.
2 points
0 issues
353 views
0 points
0 issues
133 views
Contents