Source author record

Alantha Newman

Alantha Newman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics

Catalog footprint

What is connected

6works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a $θ$-cyclic point: $x_e \in \{0,θ, 1-θ, 1\}$, where the support graph is subcubic and each vertex is incident to at least one edge with $x$-value 1. Such points are sufficient to resolve TSP in general. For these points, we construct a convex combination of tours in which we can reduce the usage of edges with $x$-value 1 from the $\frac{3}{2}$ of Christofides algorithm to $\frac{3}{2}-\fracθ{10}$ while keeping the usage of edges with fractional $x$-value the same as Christofides algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP: In the case when the objective function of the subtour elimination relaxation is minimized by a $\frac{2}{3}$-uniform point: $x_e \in \{0, \frac{2}{3}\}$, we give a $\frac{17}{12}$-approximation algorithm for TSP. For such points, this lands us halfway between the approximation ratios of $\frac{3}{2}$ of Christofides algorithm and $\frac{4}{3}$ implied by the famous "four-thirds conjecture".

preprint2020arXiv

An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs

Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yields 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 $25/18$ on subquartic graphs. To prove this, we present different methods to upper bound the minimum cost of a circulation on the network $C(G,T)$. Our approximation guarantee holds for all graphs that have an optimal solution to a standard linear programming relaxation of graph-TSP with subquartic support.

preprint2014arXiv

Graph-TSP from Steiner Cycles

We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of vertices. For a graph $G$, if we can find a spanning tree $T$ and a simple cycle that contains the vertices with odd-degree in $T$, then we show how to combine the classic "double spanning tree" algorithm with Christofides' algorithm to obtain a TSP tour of length at most $\frac{4n}{3}$. We use this approach to show that a graph containing a Hamiltonian path has a TSP tour of length at most $4n/3$. Since a Hamiltonian path is a spanning tree with two leaves, this motivates the question of whether or not a graph containing a spanning tree with few leaves has a short TSP tour. The recent techniques of Mömke and Svensson imply that a graph containing a depth-first-search tree with $k$ leaves has a TSP tour of length $4n/3 + O(k)$. Using our approach, we can show that a $2(k-1)$-vertex connected graph that contains a spanning tree with at most $k$ leaves has a TSP tour of length $4n/3$. We also explore other conditions under which our approach results in a short tour.

preprint2014arXiv

On the Configuration LP for Maximum Budgeted Allocation

We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of $m$ indivisible goods to $n$ players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of $\frac{3}{4}$, which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than $\frac{3}{4}$, and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the Restricted Budgeted Allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from $\frac{5}{6}$ to $2\sqrt{2}-2\approx 0.828$ and also prove hardness of approximation results for both cases.

preprint2011arXiv

A counterexample to Beck's conjecture on the discrepancy of three permutations

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy Omega(log(n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck's conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy O(sqrt(l)).

preprint2010arXiv

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus on Algorithmic Foundations of the Internet, and the Center for Computational Intractability with support from the National Security Agency and the National Science Foundation. The speakers at the tutorial were Matthew Andrews, Sanjeev Arora, Moses Charikar, Prahladh Harsha, Subhash Khot, Dana Moshkovitz and Lisa Zhang. The sribes were Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard and Gwen Spencer.