74 research outputs found
Approximating the maximum acyclic subgraph
No full textThesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.Includes bibliographical references (leaf 33).by Alantha Newman.S.M
Algorithms for string and graph layout
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 121-125).Many graph optimization problems can be viewed as graph layout problems. A layout of a graph is a geometric arrangement of the vertices subject to given constraints. For example, the vertices of a graph can be arranged on a line or a circle, on a two- or three-dimensional lattice, etc. The goal is usually to place all the vertices so as to optimize some specified objective function. We develop combinatorial methods as well as models based on linear and semidefinite programming for graph layout problems. We apply these techniques to some well-known optimization problems. In particular, we give improved approximation algorithms for the string folding problem on the two- and three-dimensional square lattices. This combinatorial graph problem is motivated by the protein folding problem, which is central in computational biology. We then present a new semidefinite programming formulation for the linear ordering problem (also known as the maximum acyclic subgraph problem) and show that it provides an improved bound on the value of an optimal solution for random graphs. This is the first relaxation that improves on the trivial "all edges" bound for random graphs.by Alantha Newman.Ph.D
Complex Semidefinite Programming and Max-k-Cut
No full textIn a second seminal paper on the application of semidefinite
programming to graph partitioning problems, Goemans and Williamson
showed in 2004 how to formulate and round a complex semidefinite program to give what is to date still the best-known approximation guarantee of .836008 for Max-3-Cut. (This approximation ratio was also achieved independently around the same time by De Klerk et
al..) Goemans and Williamson left open the problem of how to apply their techniques to Max-k-Cut for general k. They point out that it does not seem straightforward or even possible to formulate a good quality complex semidefinite program for the general Max-k-Cut problem, which presents a barrier for the further application of their techniques.
We present a simple rounding algorithm for the standard semidefinite
programmming relaxation of Max-k-Cut and show that it is equivalent to the rounding of Goemans and Williamson in the case of Max-3-Cut. This allows us to transfer the elegant analysis of Goemans and Williamson for Max-3-Cut to Max-k-Cut. For k > 3, the resulting approximation ratios are about .01 worse than the best known guarantees. Finally, we present a generalization of our rounding algorithm and conjecture (based on computational observations) that it matches the best-known guarantees of De Klerk et al
Coloring Tournaments with Few Colors: Algorithms and Complexity
No full textA k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds.
We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments
An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
No full textInternational audienceRecently, Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yielded a 4 3 -approximation guarantee on subcubic graphs as well as a substantial improvement over the 3 2 -approximation guarantee of Christofides' algorithm on general graphs. The crux of their approach is to compute an upper bound on the minimum cost of a circulation in a particular network, C(G, T), where G is the input graph and T is a carefully chosen spanning tree. The cost of this circulation is directly related to the number of edges in a tour output by their algorithm. Mucha subsequently improved the analysis of the circulation cost, proving that Mömke and Svensson's algorithm for graph-TSP has an approximation ratio of at most 13 9 on general graphs. This analysis of the circulation is local, and vertices with degree four and five can contribute the most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph with degree at most four at each vertex) for which Mucha's analysis of the Mömke-Svensson algorithm is tight. We show that this is not the case and that Mömke and Svensson's algorithm for graph-TSP has an approximation guarantee of at most 46 33 on subquartic graphs. To prove this, we present a different method to upper bound the minimum cost of a circulation on the network C(G, T). Our approximation guarantee actually holds for all graphs that have an optimal solution to a standard linear programming relaxation of graph-TSP with subquartic support
Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding
No full textWe consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i) no edge is monochromatic, and (ii) each edge has a unique maximum color. It is an open question as to whether or not a 2-LO colorable 3-uniform hypergraph can be LO colored with 3 colors in polynomial time. Nakajima and Živný recently gave a polynomial-time algorithm to color such hypergraphs with Õ(n^{1/3}) colors and asked if SDP methods can be used directly to obtain improved bounds. Our main result is to show how to use SDP-based rounding methods to produce an LO coloring with Õ(n^{1/5}) colors for such hypergraphs. We show how to reduce the problem to cases with highly structured SDP solutions, which we call balanced hypergraphs. Then we discuss how to apply classic SDP-rounding tools in this case to obtain improved bounds
Towards Improving Christofides Algorithm for Half-Integer TSP
No full textWe study the traveling salesman problem (TSP) in the case when the objective function of the subtour linear programming relaxation is minimized by a half-cycle point: x_e in {0,1/2,1} where the half-edges form a 2-factor and the 1-edges form a perfect matching. Such points are sufficient to resolve half-integer TSP in general and they have been conjectured to demonstrate the largest integrality gap for the subtour relaxation.
For half-cycle points, the best-known approximation guarantee is 3/2 due to Christofides' famous algorithm. Proving an integrality gap of alpha for the subtour relaxation is equivalent to showing that alpha x can be written as a convex combination of tours, where x is any feasible solution for this relaxation. To beat Christofides' bound, our goal is to show that (3/2 - epsilon)x can be written as a convex combination of tours for some positive constant epsilon. Let y_e = 3/2-epsilon when x_e = 1 and y_e = 3/4 when x_e = 1/2. As a first step towards this goal, our main result is to show that y can be written as a convex combination of tours. In other words, we show that we can save on 1-edges, which has several applications. Among them, it gives an alternative algorithm for the recently studied uniform cover problem. Our main new technique is a procedure to glue tours over proper 3-edge cuts that are tight with respect to x, thus reducing the problem to a base case in which such cuts do not occur
An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs
No full textTHL
Recent Progress on Graph TSP
No full textThis is recent work and preprint will be available at the time of the conference.National audienceWe give an overview of some recent progress on designing approximationalgorithms for the Graph TSP problem focusing on the recentbreakthrough algorithm by Moemke and Svensson. The worst caseapproximation guarantee of this algorithm was shown by Mucha to be13/9. We then present an improved analysis of this algorithm for thecase of subquadratic graphs, i.e. graphs with maximum degree four.</p
An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs (Journal Version)
No full textInternational audienceMoemke and Svensson presented a beautiful new approach for the traveling salesman problemon a graph metric (graph-TSP), which yields a 4/3-approximation guarantee on subcubic graphsas well as a substantial improvement over the 3/2-approximation guarantee of Christofides’algorithm on general graphs. The crux of their approach is to compute an upper bound on theminimum cost of a circulation in a particular network,C(G, T), whereGis the input graphandTis a carefully chosen spanning tree. The cost of this circulation is directly related tothe number of edges in a tour output by their algorithm. Mucha subsequently improved theanalysis of the circulation cost, proving that Moemke and Svensson’s algorithm for graph-TSPhas an approximation ratio of at most 13/9 on general graphs.This analysis of the circulation is local, and vertices with degree four or five can contributethe most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph withdegree at most four at each vertex) for which Mucha’s analysis of the M ̈omke-Svensson algorithmis tight. We show that this is not the case and that M ̈omke and Svensson’s algorithm for graph-TSP has an approximation guarantee of at most 25/18 on subquartic graphs. To prove this,we present different methods to upper bound the minimum cost of a circulation on the networkC(G, T). Our approximation guarantee holds for all graphs that have an optimal solution for astandard linear programming relaxation of graph-TSP with subquartic support
- …
