** 1. Approximation algorithms
**

I am a problem solver: I design algorithms. An algorithm for optimization must produce output

- that satisfies constraints (
*feasibility*) - that optimizes (minimizes or maximizes) an objective function.

Such problems are often NP-hard. So we look for a solution that is not exact but close to optimum.

Example 1TSP (Travelling Salesman Problem). The input is cities. The output is a tour that visits each city exactly once. The objective is minimizing the total length.

This is NP-hard (the term “NP-complete” may only be applied to decision problems, whose output is “yes” or “no”).

The quality of an approximate solution is measured by relative error. Here’s the definition for minimization; the definition for maximization is similar.

Definition 1A (c,s)-approximation, for a minimization problem, means that if , then output value is . An -approximation is short for -approximation for all .

The idea is to use minimum spanning tree double cover. More precisely, using a greedy algorithm, compute a minimum cost tree spanning all cities (add edges in the order of increasing distances, maintaining an acyclic structure). Double each edge, this gives an Eulerian graph (connected and all degrees are even). Find an Eulerian tour (traverses every edge exactly once), and to build a tour, follow the Eulerian tour, jumping (shortcuts) when the Eulerian tour lets you pass by a point already visited.

**Claim**.

**Proof of the claim**. By construction,

and

TSP is one of the 21 problems that Richard Karp proved to be NP complete. So a -approximation cannot be given in polynomial time if PNP. Our goal is to get as closed to as possible. The best we can hope is to get arbitrarily close to :

*, poly-time algorithm giving a -approximation. *

Such a family of algorithms are called an *approximation scheme*. In some sense, problems that have an approximation scheme are the easiest among NP-hard combinatorial problems.

Example 3KNAPSACK. Given objects, each with a value and a volume, you want to put as much value as possible in your knapsack without exceeding the knapsack’s capacity.

KNAPSACK admits an approximation scheme.

Some problems do not admit approximation schemes (if PNP).

Example 4MAX CLIQUE. Input: a graph. Output: a clique (complete graph embedded in given graph). Objective: size, i.e number of vertices of clique.

MAX CLIQUE is NP-hard (Karp). Worse, if PNP, , one cannot find a clique of size in polynomial time.

In the 1970’s, people explored hundreds of decision problems and classified them in P or NP-hard. These days, one deals with optimization problems, and one tries to classify them according to hardness of approximation.

**2. A case study: approximation algorithms for SET COVER **

**Example 5** * SET COVER. Cover a set with the cheapest subsets. Input: a finite set of elements, a collection of subsets of , each subset has a weight. Output is a covering of with elements of . Objective: the sum of the weights of the chosen sets. *

SET COVER is NP-hard. Let us give an approximation algorithm based on Linear Programming.

**2.1. A linear programming relaxation for SET COVER**

1. (Integer program.) Give a model for SET COVER as an integer program. Let , , weight of . Output is a \{ 0,1 \} vector ( iff we use in the covering). Let iff . This matrix encodes the ‘s. We assume that the ‘s cover. The constraint that the chosen ‘s cover is (i.e. each entry is ). The goal is to minimize .

2. (Linear program.) We are stuck since integer programming (solving the linear program for an integer valued unknown vector x) is NP-hard. So we drop the integrality constraint and replace it with . The resulting LP has a poly-time solution .

**2.2. A first algorithm using deterministic rounding
**

3. (Rounding.) If is integral, done. If not, round to the nearest integer, or .

(Analysis.) Does cover, i.e. ? Not in general. For instance, if all ‘s appear thrice with equal weights, the solution is divided by , all are , and so .

Theorem 2Let denote the maximum, over all elements of , of the number of sets of containing it. Then there is an -approximation.

*Proof:* (Algorithm:) Modify third step as follows.

3. (Rounding) Choose a and round to if , to otherwise.

(Analysis:) Check that the output covers every element: Pick an element . The LP solution satisfies . By assumption, bounds the number of ‘s in that row. This implies that at least one of the involved is . So as long as is such that , at least one of the involved is equal to , and is covered.

The weight of the output is .

Conclusion. If one takes , the rounded solution covers and its weight is .

**2.3. A second algorithm using randomized rounding **

Modify third step as follows.

3. (Rounding) For all , include independently with probability .

and with probability , every element is covered.

*Proof:*

Note that . We know that is (fractionnally) covered by the LP solution, i.e. . Thus

Therefore , and

** 2.4. Epilogue **

Take , this gives approximation, with high probability when c is strictly greater than 1. Can we do better ?

Theorem 4If PNP, there exists a constant such that no polynomial algorithm can give a -approximation for SET COVER.

This is a result of Raz-Safra, 1997, [RS], improving on Lund-Yannakakis 1990 [LY]. Later on, Uriel Feige (1998) has been able to pin down the exact constant. He proved that under a slight strengthening of PNP, [F].

To summarize, the technique goes as follows.

- Express problem as integer linear program.
- Solve a LP relaxation.
- Round deterministically or randomly the solution to make it integral but still feasible.

** **

**3. Solving linear or semi-definite programs **

One might skip this subsection and keep LP/SDP solvers as a black box. Claire would prefer so (she has not prepared this part well), but audience is eager to know more…

Geometrically, an LP problem amounts to the input of a convex polytope (intersection of the half-spaces defined by linear inequalities, convex since intersection of convexes) and a linear function. The goal is to maximize the linear function on the polytope.

** 3.1. The simplex method **

The simplex algorithm is of the greedy type: walk from vertex to vertex, choosing the steepest ascending edge, until a local optimum is reached. Complexity can be exponential, since the number of vertices of the polytope can be exponential. However, it works well in practice, i.e. on data arising in applications. (Note that one must also take care to deal with special cases such as the polytope being empty or unbounded.)

** 3.2. The ellipsoid method **

Khachyian 1979 for the analysis. This is polynomial time ( where is the number of digits needed to express data).

Let us first assume that our goal is just to find a feasible solution (we shall see later on why this helps solving the optimisation problem).

Assume that we are given a starting ellipsoid that contains the entire polytope . An ellipsoid is defined by an inequation of the form , positive definite symmetric. If , we are done. If not, we find a constraint of the LP that violates, i.e. a half-space containing which is disjoint from . Now has volume . There is a new ellipsoid that contains (and thus ), and its volume is . After a few steps, one can prove that the center of the ellipsoid is contained in . For this, one needs a lower bound on . This involves some preprocessing – if one of the constraints is an equality constraint, we can use it to eliminate a variable and reduce dimensions.

HELP! Please complete…

In the end, running time is polynomial in the number of constraints.

The optimisation problem is solved as follows. Start from a point of . Add a constraint parallel to the linear function. Previous algorithm gives new point of with better value.

HELP! Please complete…

** 3.3. Generalisation **

Note that all that is needed for the ellipsoid method is a *separation oracle*, which says whether a point belongs to , and if not, provides a separating hyperplane. So the method sometimes applies to problems with an exponential number of constraints.

Example 6MINIMUM SPANNING TREE. Input : a graph with edge weights. Output: a subset of edges connecting all the vertices. Objective: total weight.

This is equivalent the following IP: Let according to whether we take edge or not. Connectivity constraint is

Objective: .

There are exponentially many constraints. But there is a poly-time separation oracle for the LP-relaxation. Indeed, use the max-flow/min-cut theorem. , , compute in graph where edge has capacity .

- if this cut has value , then it gives a violated constraint.
- otherwise, i.e. if all cuts have values , we have a solution.

**3.4. Semi-definite programming **

In a semi-definite program, the unknowns are coded into a square matrix and the constraints in the fact that is positive semi-definite (plus a few linear constraints).

Recall the four equivalent conditions for a real symmetric matrix to be positive semi-definite: depending on the algorithm and analysis, we will need one or the other of the characterizations.

Is there a separation oracle ? Yes, using linear algebra. The question is: how do we test whether a matrix is positive semi-definite, and give a separating hyperplane if the answer is negative? One answer is to build a Cholesky decomposition A=VV* (using a version of Gaussian elimination). Other answers are discussed on http://math.stackexchange.com/questions/13282/determining-whether-a-symmetric-matrix-is-positive-definite-algorithm.

**4. Using SDP for approximation algorithms: MAX CUT **

**Example 7** MAX CUT. Input: a graph with edge weight. Output: a partition of the vertices. Goal: maximize .

**Remarks**. 1. This is NP-hard. Note that if max is replaced by min, there is a polynomial solution.

2. Using linear programs, we do not know how to improve on this.

3. Goemans and Williamson, 1994, [GW], have used an SDP to prove the following theorem.

Theorem 5There is a 0.878..-approximation algorithm for MAX CUT.

*Proof:* Let us try to turn this into an LP. Take as unknown -valued functions on vertices (equivalent to 0 1 integer variables, up to a linear transform). Then one must maximize . This is not linear. Failure.

1. (SDP relaxation) Remember the following criterion for semi-definiteness:

If our unknowns are vectors (columns of ), then an SDP can accomodate an objective function and constraints which are linear in inner products, like

- objective , and
- constraints .

The solution of the SDP exactly solves MAX CUT iff its rank is equal to , i.e. is a column vector. If not, the SDP solution produces a bunch of unit vectors in for some number of vertices.

2. (Randomized rounding) The rounding procedure (partitionning points on the unit sphere of ) consists in picking a random hyperplane through the origin, vectors on one side go to , vectors on the other side go to . This is a cut.

(Analysis) Let us evaluate the expectation of objective

where is the angle between and . On the other hand, the value of the SDP (which is ), is

Analysis gives that for all ,

thus

A striking, though conditional, result of S. Khot, G. Kindler, E. Mossel, R. O’Donnell 2007, [KKMO], asserts that the Goemans-Williamson approximability bound could be sharp.

Theorem 6If UGC holds, then no poly-time algorithm can -approximate MAX CUT if .

Now you want to understand UGC ? Come on friday, 3pm, in Jussieu, b\^atiment Atrium, ground floor, grand salle de visioconference, and listen to Subhash Khot. And attend Sanjeev Arora’s mini-course in Amphi Hermite the week after.

** References **

[F] Feige, Uriel , * A threshold of for approximating set cover.* J. ACM **45** (1998), no. 4, 634–652.

[GW] Goemans, Michel X.; Williamson, David P.; * Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.* J. ACM **42** (1995), no. 6, 1115–1145.

[KKMO] Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan; * Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?* SIAM J. Comput. **37** (2007), no. 1, 319–357.

[LY] Lund, Carsten; Yannakakis, Mihalis; * On the hardness of approximating minimization problems.* J. ACM **41** (1994), no. 5, 969–981.

[RS] Raz, Ran; Safra, Shmuel; * A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP.* STOC ’97 (El Paso, TX), 475–484 (electronic), ACM, New York, 1999.

Richard M. Karp (1972). “Reducibility Among Combinatorial Problems“. In R. E. Miller and J. W. Thatcher (editors). *Complexity of Computer Computations*. New York: Plenum. pp. 85–103.