An O(log n / loglog n)-approximation algorithm for the Asymmetric Travelling Salesperson problem

In this Thursday's seminar, we will go over the recent SODA 2010 paper which gives an O(log n/loglog n)-approximation algorithm for the Asymmetric Travelling Salesperson (ATSP) problem (paper link), improving over the 1982 result of Frieze et al, which showed an O(log n)-approximation for the problem. In contrast, the symmetric version has seen much better approximations, with the best known being a factor 3/2 algorithm due to Christofedes.

In the ATSP problem, we are given a directed graph with cost on the arcs, and these costs satisfy the triangle inequality, i.e c(u,w) <= c(u,v) + c(v,u). Note that the arc costs need not be symmetric, i.e c(u,v) != c(v,u). The goal is to find a minimum cost cycle which visits all the vertices of the graph.

Since 1928 (until this paper), the best known approximation for this problem has been due to Frieze et al, who give a simple combinatorial algorithm and neat analysis to prove a logarithmic approximability bound. They also bound the integrality gap of the natural LP relaxation for the problem.

In the recent paper, Asadpour et al. consider the same LP and give an improved algorithm (based on rounding the LP) which betters the approximation factor by a factor of loglog n. At a high level, their algorithm does the following:

(i) solve the LP, (ii) ignore arc directions for the time being, and get a fractional solution in the spanning tree polytope, (iii) randomly round this fractional solution to get a random spanning tree which satisfies some thin-ness properties, (iv) re-direct these edges appropriately, (v) augment some extra edges to get back euler tour along the directed arcs.

In the lecture, we will first go over the Christofedes algorithm for STSP and then the Frieze et al. algorithm for ATSP. Then we will present the LP and explain its structural properties. Before presenting the rounding process, we will take a detour into the world of matroids and their associated polytopes and present some recent work of Chekuri et al. on how to round a random point in a matroid polytope into a good vertex solution that satisfies some nice properties. Subsequently, we will use these techniques and give the complete details of their approximation algorithm. We will conclude by explaining the connections with steps (iv) and (v) with the algorithm of Christofedes for the STSP.

For a graph $G = (V,E)$ with $|V|=n$, the Laplacian of $G$,

\[L = L_G = D_G - A_G,\]

is an $n \times n$ matrix where $A_G$ is the adjacency matrix of $G$ and $D_G$ is a diagonal matrix consisting of the degrees of vertices of $G$. $L$ is real, symmetric and positive semi-definite and has $n$ real eigenvalues usually enumerated as

\[ 0 = \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n.\]

The spectrum of $L$, in particular $\lambda_2$, also called the Fiedler value, is related to the connectedness of $G$ and spectral methods are heavily used in heuristics for graph partitioning and its variants. For this reason, $\lambda_2$ has been the focus of much theoretical work.

Most results on $\lambda_2$ were obtained by working with some embedding of a graph onto a surface and exploiting connections between the Fiedler value and geometric embeddings. As such, these techniques were specialized to graphs endowed with some structure which allow one to find an external geometric representation. See, for example, Kelner .

In 2008, Biswal, Lee, and Rao presented a method for bounding $\lambda_2$ using an intrinsic deformation of the graph. This deformation is achieved by assigning weights to vertices and equipping $V$ with a shortest path metric. A parameter associated with the metric (essentially, the average pairwise distance) is used to upper bound the Fiedler value and this parameter is optimized over all weight functions. Interestingly, this optimization problem has a dual formulation in terms of all pairs multi-commodity flows, where the optimal weights on vertices correspond directly to a measure of congestion in the optimal flow. The results are obtained by studying the structure of optimal flows in various classes of graphs.

The paper I will be discussing, ``Higher Eigenvalues of Graphs'' by Kelner, Lee, Price, and Teng, extends the above result to obtain bounds on higher eigenvalues. Additional conditions in the optimization problem lead to restrictions in the dual formulation and the notion of subset multi-commodity flows is introduced. Working under this setup, the authors show that $\lambda_k$ is $O(k/n)$ for planar graphs, $O(g k / n)$ for graphs of genus $g$, and $O(h^2 \log (h) k / n)$ for graphs with excluded $K_h$-minors.

Twice Ramanujan Sparsifiers

Given a weighted graph G, a natural question to ask is whether there exist another graph H on the same vertex set such that any cut has similar weights in G and H. As the weight of a cut can be described by $\sum_{uv \in E(G)}w_{uv}(x_u-x_v)^2$ where x is a 0-1 vector, one could ask the same question where x can take any real values. A spectral sparsifier for a graph G is H such that the above functions on the two graphs are close for any assignment of x and H is sparse.

Algorithmically, graph sparsifiers were first studied as a subroutine for near-linear time Laplacian Solvers by Spielman and Teng. Their algorithm partitions the graph into expanders by finding approximately sparse cuts, then randomly sampling each expander.

Follow up work has been done on other methods for finding sparsifiers that give better guarantees. One approach is to sample the edges by effective resistance, but it relies on the near-linear time solver to achieve good performance. This work uses a similar approach, but with a different goal in mind. It aims to find the best approximation rate possible with a d-regular subgraph, and achieves twice the ratio given by Ramanujan graphs , which are regular graphs whose spectral gap are as large as possible.

I will use the first half of the talk to cover background topics such as condition number and spectral decompositions, then show the approaches used in recent work on sparsifiers. If time permit, I will try to give a sketch of why one couldn't do better than the ratios given by Ramanujan graphs. The second half of the talk will be used to go through the proof of the key theorem of this paper, which basically states the following:
Given a set of rank one matrices that sum to identity, one could pick a small subset of them such that the ratio between the largest and smallest eigenvalues of their sum is small.

The Role of Randomization in Mechanism Design

On Thursday I will talk about the FOCS 2009 paper of Dobzinksi and Dughmi, "On The Power of Randomization in Algorithmic Mechanism Design" (link). This blog post serves as a teaser.

First of all, what is mechanism design? Mechanism design is just combinatorial optimization, for which the input to the problem instance is controlled by a set of self-interested parties who might lie about their data if lying proves to be advantageous. The challenge of mechanism design is therefore not only to design an algorithm that finds a good solution to its given input, but also to do so in such a way so that all of the self-interested parties are incentivized to report their true data to the mechanism.

Auctions represent the canonical mechanism design problem: The auctioneer has a set of goods to distribute among n bidders, and the bidders each have a valuation function that determines how much utility they would receive from each subset of the goods. One common objective for a mechanism designer is to distribute the items so as to maximize social welfare: the sum utilities of all of the bidders. In addition to being able to distribute the goods, the mechanism is given the power to charge bidders some price, up to their reported valuation for the set of goods they ultimately receive.

When do there exist mechanisms to optimize social welfare? The Vickrey Auction, introduced in the early 1960s, and later generalized into the VCG Mechanism by Clarke and Groves in the 1970s gives the answer: almost always. Under quite weak conditions, the VCG mechanism defines prices which incentivize agents to report truthfully when the mechanism computes the optimal allocation given the reports. This is great news, and Vickrey won the Nobel Prize for this in 1996. But it doesn't quite close the book on social welfare maximization. The VCG mechanism requires the auctioneer to actually calculate the optimal allocation to maximize social welfare, and so when the welfare maximization problem is itself computationally difficult, it is not possible to implement the VCG mechanism. Unfortunately, the incentive properties of the VCG mechanism depend on the output allocation actually being optimal: this means that approximation algorithms for combinatorial optimization problems don't easily translate into truthful mechanisms which approximately maximize social welfare.

This brings us to one of the motivating questions for algorithmic mechanism design: When exact optimization of social welfare is a computationally difficult problem, when do there exist computationally efficient truthful algorithms which well approximate optimal social welfare? This paper considers the role that randomization plays in the answer to this question.

Lets revisit what truthful means. For a deterministic mechanism to be truthful, no matter what the reported data of the other agents, no agent i should ever be able to manipulate the mechanism by lying about his own data so as to cause the mechanism to select an outcome he prefers. There are two ways that we can generalize this to randomized mechanisms:

1. A universally truthful randomized mechanism is simply a probability distribution over deterministic truthful mechanisms. The mechanism gets to flip some coins, but no matter what the outcome of the coins, no agent could have benefited by lying, even in hindsight.
2. A truthful in expectation mechanism only guarantees that no agent can benefit in expectation by lying, before the mechanism's coins are flipped. For some outcomes of the coins in hindsight, agents could possibly have benefited by lying.

Universally truthful mechanisms give the stronger guarantee: they do not require that we assume that agents are risk neutral and only wish to maximize their expected welfare, independent of risk. But when we do have risk neutral bidders, can we provide better approximations for some problems using truthful in expectation mechanisms?

This paper proves a separation which answers the question: yes. Dobzinski and Dughmi demonstrate an auction problem with m items for which they prove:

• For any epsilon > 0, there exists a truthful in expectation mechanism which achieves a (1+epsilon) approximation to social welfare and runs in time poly(1/epsilon, log m).
• For any constant epsilon > 0 any universally truthful mechanism that achieves a (2-epsilon) approximation to social welfare must run in time Omega(m).

The negative result is a communication complexity lower bound, and so holds independently of computational constraints.

The auction for which the separation is proved is somewhat artificial, but nevertheless shows that the class of efficient truthful in expectation mechanisms is strictly broader than the class of efficient universally truthful mechanisms. This should be viewed analogously to a complexity-class separation in how it shapes our understanding of the power of efficient truthful mechanisms.

So. Come to class on Thursday to hear more!