- You are here:
- GT Home
- Home
- News & Events

Series: ACO Colloquium

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.This is joint work with Ola Svensson and Jakub Tarnawski.

Series: ACO Colloquium

Given a graph H, the Turan graph problem asks to find the maximum number of
edges in a n-vertex graph that does not contain any subgraph isomorphic to
H. In recent years, Razborov's flag algebra methods have been applied to
Turan hypergraph problems with great success. We show that these techniques
embed naturally in standard symmetry-reduction methods for sum of squares
representations of invariant polynomials. This connection gives an
alternate computational framework for Turan problems with the potential to
go further. Our results expose the rich combinatorics coming from the
representation theory of the symmetric group present in flag algebra
methods.
This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.

Series: ACO Colloquium

Refreshments will be served in the atrium after the talk.

The sign-rank of a real matrix A with no 0 entries is the
minimum rank of a matrix B so that A_{ij}B_{ij} >0 for all i,j. The
study of this notion combines combinatorial, algebraic, geometric
and probabilistic techniques with tools from real algebraic geometry,
and is related to questions in Communication Complexity, Computational
Learning and Asymptotic Enumeration. I will discuss the topic and describe
its background, several recent results from joint work with Moran and
Yehudayoff, and some intriguing open problems.

Series: ACO Colloquium

Refreshments will be served in the atrium immediately following the talk. Please join us to welcome the new class of ACO students.

Graph immersion is an alternate model for graph containment similar to graph minors or topological minors. The presence of a large clique immersion in a graph G is closely related to the edge connectivity of G. This relationship gives rise to an easy theorem describing the structure of graphs excluding a fixed clique immersion which serves as the starting point for a broader structural theory of excluded immersions. We present the highlights of this theory with a look towards a conjecture of Nash-Williams on the well-quasi-ordering of graphs under strong immersions and a conjecture relating the chromatic number of a graph and the exclusion of a clique immersion.

Series: ACO Colloquium

It is well known that many optimization
problems, ranging from linear programming to hard combinatorial
problems, as well as many engineering and economics problems, can be
formulated as linear complementarity
problems (LCP). One particular problem, finding a Nash equilibrium of a
bimatrix game (2 NASH), which can be formulated as LCP, motivated the
elegant Lemke algorithm to solve LCPs. While the algorithm always
terminates, it can generates either a solution
or a so-called ‘secondary ray’. We say that the algorithm resolves
a given LCP if a secondary ray can be used to certify, in polynomial
time, that no solution exists. It turned out that in general,
Lemke-resolvable LCPs belong to the complexity class
PPAD and that, quite surprisingly, 2 NASH is PPAD-complete. Thus,
Lemke-resolvable LCPs can be formulated as 2 NASH. However, the known
formulation (which is designed for any PPAD problem) is very
complicated, difficult to implement, and not readily available
for potential insights. In this talk, I’ll present and discuss a simple
reduction of Lemke-resolvable LCPs to bimatrix games that is easy to
implement and have the potential to gain additional insights to problems
(including several models of market equilibrium)
for which the reduction is applicable.

Series: ACO Colloquium

Tree codes are the basic underlying combinatorial object in the interactive coding theorem, much as block error-correcting codes are the underlying object in one-way communication. However, even after two decades, effective (poly-time) constructions of tree codes are not known. In this work we propose a new conjecture on some exponential sums. These particular sums have not apparently previously been considered in the analytic number theory literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications. (Joint work with Cris Moore.)

Series: ACO Colloquium

We will outline the proof that gives a positive solution to Weaver's conjecture $KS_2$. That is, we will show that any isotropic collection of vectors whose outer products sum to twice the identity can be partitioned into two parts such that each part is a small distance from the identity. The distance will depend on the maximum length of the vectors in the collection but not the dimension (the two requirements necessary for Weaver's reduction to a solution of Kadison--Singer). This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials." This talk is intended to be accessible by a general mathematics audience, and represents joint work with Dan Spielman and Nikhil Srivastava.

Series: ACO Colloquium

(Refreshments in the lounge outside Skiles 005 at 4:05pm)

This is a survey of Hub Labeling results for general and road networks.Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by [Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set systems have small VC-dimension.Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks.The simplicity of HL queries allows their implementation inside of a relational database (e.g., in SQL), and query efficiency assures real-time response. Furthermore, including HL data in the database allows efficient implementation of more sophisticated location-based queries. These queries can be combined with traditional SQL queries. This approach brings the power of location-based services to SQL programmers, and benefits from external memory implementation and query optimization provided by the underlying database.Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.

Series: ACO Colloquium

Refreshments at 10:30am in the atrium outside Skiles 006

The traveling salesman problem (TSP) is the most famous problem in
discrete optimization. Given $n$ cities and the costs $c_{ij}$ for
traveling from city $i$ to city $j$ for all $i,j$, the goal of the
problem is to find the least expensive tour that visits each city
exactly once and returns to its starting point. We consider cases in
which the costs are symmetric and obey the triangle inequality. In
1954, Dantzig, Fulkerson, and Johnson introduced a linear programming
relaxation of the TSP now known as the subtour LP, and used it to find
the optimal solution to a 48-city instance. Ever since then, the
subtour LP has been used extensively to find optimal solutions to TSP
instances, and it is known to give extremely good lower bounds on the
length of an optimal tour.
Nevertheless, the quality of the subtour LP bound is poorly understood
from a theoretical point of view. For 30 years it has been known that
it is at least 2/3 times the length of an optimal tour for all instances
of the problem, and it is known that there are instances such that it
is at most 3/4 times the length of an optimal tour, but no progress has
been made in 30 years in tightening these bounds.
In this talk we will review some of the results that are known about the
subtour LP, and give some new results that refine our understanding in
some cases. In particular, we resolve a conjecture of Boyd and Carr
about the ratio of an optimal 2-matching to the subtour LP bound in the
worst case. We also begin a study of the subtour LP bound for the
extremely simple case in which all costs $c_{ij}$ are either 1 or 2.
For these instances we can show that the subtour LP is always strictly
better than 3/4 times the length of an optimal tour.
These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.

Series: ACO Colloquium

Motivated by mass-spectrometry protein sequencing,
we consider the simple problem of reconstructing
a string from its substring compositions. Relating
the question to the long-standing turnpike problem,
polynomial factorization, and cyclotomic polynomials,
we cleanly characterize the lengths of reconstructable
strings and the structure of non-reconstructable ones.
The talk is elementary and self contained and covers
work with Jayadev Acharya, Hirakendu Das, Olgica
Milenkovic, and Shengjun Pan.