CS359G Lecture 7: Computing Eigenvectors

In which we analyze a nearly-linear time algorithm for finding an approximate eigenvector for the second eigenvalue of a graph adjacency matrix, to be used in the spectral partitioning algorithm.

In past lectures, we showed that, if is a -regular graph, and is its normalized adjacency matrix with eigenvalues , given an eigenvector of , the algorithm SpectralPartition finds, in nearly-linear time , a cut such that .

More generally, if, instead of being given an eigenvector such that , we are given a vector such that , then the algorithm finds a cut such that . In this lecture we describe and analyze an algorithm that computes such a vector using arithmetic operations.

A symmetric matrix is positive semi-definite (abbreviated PSD) if all its eigenvalues are nonnegative. We begin by describing an algorithm that approximates the largest eigenvalue of a given symmetric PSD matrix. This might not seem to help very much because the adjacency matrix of a graph is not PSD, and because we want to compute the second largest, not the largest, eigenvalue. We will see, however, that the algorithm is easily modified to approximate the second eigenvalue of a PSD matrix (if an eigenvector of the first eigenvalue is known), and that the adjacency matrix of a graph can easily be modified to be PSD.

CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube

In which we talk about the spectrum of Cayley graphs of abelian groups, we compute the eigenvalues and eigenvectors of the cycle and of the hypercube, and we verify the tightness of the Cheeger inequalities and of the analysis of spectral partitioning

In this lecture we will prove the following results:

1. The dimension- hypercube has and , giving an infinite family of graphs for which , showing that the first Cheeger inequality is exactly tight.
2. The -cycle has , and , giving an infinite family of graphs for which , showing that the second Cheeger inequality is tight up to a constant.
3. There is an eigenvector of the second eigenvalue of the hypercube , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut of expansion , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.

CS359G Lecture 5: Characters of Abelian Groups

In which we introduce the theory of characters of finite abelian groups, which we will use to compute eigenvalues and eigenvectors of graphs such as the cycle and the hypercube

In the past lectures we have established the Cheeger inequalities

and the fact that the SpectralPartitioning algorithm, when given an eigenvector of , finds a cut such that . In the next lecture we will show that all such results are tight, up to constants, by proving that

• The dimension- hypercube has and , giving an infinite family of graphs for which , showing that the first Cheeger inequality is exactly tight.
• The -cycle has , and , giving an infinite family of graphs for which , showing that the second Cheeger inequality is tight up to a constant.
• There is an eigenvector of the 2nd eigenvalue of the hypercube , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut of expansion , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.

In this lecture we will develop some theoretical machinery to find the eigenvalues and eigenvectors of Cayley graphs of finite Abelian groups, a class of graphs that includes the cycle and the hypercube, among several other interesting examples. This theory will also be useful later, as a starting point to talk about algebraic constructions of expanders.

For readers familiar with the Fourier analysis of Boolean functions, or the discrete Fourier analysis of functions , or the standard Fourier analysis of periodic real functions, this theory will give a more general, and hopefully interesting, way to look at what they already know.

CS359G Lecture 4: Spectral Partitioning

In which we prove the difficult direction of Cheeger’s inequality.

As in the past lectures, consider an undirected -regular graph , call its adjacency matrix, and its scaled adjacency matrix. Let be the eigenvalues of , with multiplicities, in non-increasing order. We have been studying the edge expansion of a graph, which is the minimum of over all non-trivial cuts of the vertex set (a cut is trivial if or ), where the expansion of a cut is

We have also been studying the (uniform) sparsest cut problem, which is the problem of finding the non-trivial cut that minimizes , where the sparsisty of a cut is

We are proving Cheeger’s inequalities:

and we established the left-hand side inequality in the previous lecture, showing that the quantity can be seen as the optimum of a continuous relaxation of , so that , and follows by the definition.

Today we prove the more difficult, and interesting, direction. The proof will be constructive and algorithmic. The proof can be seen as an analysis of the following algorithm.

Algorithm: SpectralPartitioning

• Input: graph and vector
• Sort the vertices of in non-decreasing order of values of entries in , that is let where
• Let be such that is minimal
• Output

We note that the algorithm can be implemented to run in time , assuming arithmetic operations and comparisons take constant time, because once we have computed it only takes time to compute .

We have the following analysis of the quality of the solution:

Lemma 1 (Analysis of Spectral Partitioning) Let be a d-regular graph, be a vector such that , let be the normalized adjacency matrix of , define

and let be the output of algorithm SpectralPartitioning on input and . Then

Remark 1 If we apply the lemma to the case in which is an eigenvector of , then , and so we have

which is the difficult direction of Cheeger’s inequalities.

Remark 2 If we run the SpectralPartitioning algorithm with the eigenvector of the second eigenvalue , we find a set whose expansion is

Even though this doesn’t give a constant-factor approximation to the edge expansion, it gives a very efficient, and non-trivial, approximation.

As we will see in a later lecture, there is a nearly linear time algorithm that finds a vector for which the expression in the lemma is very close to , so, overall, for any graph we can find a cut of expansion in nearly linear time.

CS261 Lecture 7: Rounding Linear Programs

In which we show how to use linear programming to approximate the vertex cover problem.

1. Linear Programming Relaxations

An integer linear program (abbreviated ILP) is a linear program (abbreviated LP) with the additional constraints that the variables must take integer values. For example, the following is an ILP:

Where is the set of natural numbers. The advantage of ILPs is that they are a very expressive language to formulate optimization problems, and they can capture in a natural and direct way a large number of combinatorial optimization problems. The disadvantage of ILPs is that they are a very expressive language to formulate combinatorial optimization problems, and finding optimal solutions for ILPs is NP-hard.

If we are interested in designing a polynomial time algorithm (exact or approximate) for a combinatorial optimization problem, formulating the combinatorial optimization problem as an ILP is useful as a first step in the following methodology (the discussion assumes that we are working with a minimization problem):

• Formulate the combinatorial optimization problem as an ILP;
• Derive a LP from the ILP by removing the constraint that the variables have to take integer value. The resulting LP is called a “relaxation” of the original problem. Note that in the LP we are minimizing the same objective function over a larger set of solutions, so ;
• Solve the LP optimally using an efficient algorithm for linear programming;
  • If the optimal LP solution has integer values, then it is a solution for the ILP of cost , and so we have found an optimal solution for the ILP and hence an optimal solution for our combinatorial optimization problem;
  • If the optimal LP solution has fractional values, but we have a rounding procedure that transforms into an integral solution such that for some constant , then we are able to find a solution to the ILP of cost , and so we have a -approximate algorithm for our combinatorial optimization problem.

In this lecture and in the next one we will see how to round fractional solutions of relaxations of the Vertex Cover and the Set Cover problem, and so we will be able to derive new approximation algorithms for Vertex Cover and Set Cover based on linear programming.

CS261 Lecture 6: Duality in Linear Programming

In which we introduce the theory of duality in linear programming.

1. The Dual of Linear Program

Suppose that we have the following linear program in maximization standard form:

and that an LP-solver has found for us the solution , , , of cost . How can we convince ourselves, or another user, that the solution is indeed optimal, without having to trace the steps of the computation of the algorithm?

Observe that if we have two valid inequalities

then we can deduce that the inequality

(derived by “summing the left hand sides and the right hand sides” of our original inequalities) is also true. In fact, we can also scale the inequalities by a positive multiplicative factor before adding them up, so for every non-negative values we also have

Going back to our linear program (1), we see that if we scale the first inequality by , add the second inequality, and then add the third inequality scaled by , we get that, for every that is feasible for (1),

And so, for every feasible , its cost is

meaning that a solution of cost is indeed optimal.

In general, how do we find a good choice of scaling factors for the inequalities, and what kind of upper bounds can we prove to the optimum?

CS261 Lecture 5: Linear Programming

In which we introduce linear programming.

1. Linear Programming

A linear program is an optimization problem in which we have a collection of variables, which can take real values, and we want to find an assignment of values to the variables that satisfies a given collection of linear inequalities and that maximizes or minimizes a given linear function.

(The term programming in linear programming, is not used as in computer programming, but as in, e.g., tv programming, to mean planning.)

For example, the following is a linear program.

The linear function that we want to optimize ( in the above example) is called the objective function. A feasible solution is an assignment of values to the variables that satisfies the inequalities. The value that the objective function gives to an assignment is called the cost of the assignment. For example, and is a feasible solution, of cost . Note that if are values that satisfy the inequalities, then, by summing the first two inequalities, we see that

that is,

and so no feasible solution has cost higher than , so the solution , is optimal. As we will see in the next lecture, this trick of summing inequalities to verify the optimality of a solution is part of the very general theory of duality of linear programming.

Linear programming is a rather different optimization problem from the ones we have studied so far. Optimization problems such as Vertex Cover, Set Cover, Steiner Tree and TSP are such that, for a given input, there is only a finite number of possible solutions, so it is always trivial to solve the problem in finite time. The number of solutions, however, is typically exponentially big in the size of the input and so, in order to be able to solve the problem on reasonably large inputs, we look for polynomial-time algorithms. In linear programming, however, each variable can take an infinite number of possible values, so it is not even clear that the problem is solvable in finite time.

As we will see, it is indeed possible to solve linear programming problems in finite time, and there are in fact, polynomial time algorithms and efficient algorithms that solve linear programs optimally.

There are at least two reasons why we are going to study linear programming in a course devoted to combinatorial optimization:

• Efficient linear programming solvers are often used as part of the toolkit to design exact or approximate algorithms for combinatorial problems.
• The powerful theory of duality of linear programming, that we will describe in the next lecture, is a very useful mathematical theory to reason about algorithms, including purely combinatorial algorithms for combinatorial problems that seemingly have no connection with continuous optimization.

The Wisdom of Crowds

vote or see the results

CS261 Lecture 4: TSP and Set Cover

In which we describe a -approximate algorithm for the Metric TSP, we introduce the Set Cover problem, observe that it can be seen as a more general version of the Vertex Cover problem, and we devise a logarithmic-factor approximation algorithm.

1. Better Approximation of the Traveling Salesman Problem

In the last lecture we discussed equivalent formulations of the Traveling Salesman problem, and noted that Metric TSP-R can also be seen as the following problem: given a set of points and a symmetric distance function that satisfies the triangle inequality, find a multi-set of edges such that is a connected multi-graph in which every vertex has even degree and such that is minimized.

Our idea will be to construct by starting from a minimum-cost spanning tree of , and then adding edges so that every vertex becomes of even degree.

But how do we choose which edges to add to ?

CS359G Lecture 3: Cheeger’s inequality

In which we prove the easy case of Cheeger’s inequality.

1. Expansion and The Second Eigenvalue

Let be an undirected -regular graph, its adjacency matrix, its normalized adjacency matrix, and be the eigenvalues of .

Recall that we defined the edge expansion of a cut of the vertices of as

and that the edge expansion of is .

We also defined the related notion of the sparsity of a cut as

and ; the sparsest cut problem is to find a cut of minimal sparsity.

Recall also that in the last lecture we proved that if and only if is disconnected. This is equivalent to saying that if and only if . In this lecture and the next we will see that this statement admits an approximate version that, qualitatively, says that is small if and only if is small. Quantitatively, we have

Theorem 1 (Cheeger’s Inequalities)