Schedule for: 18w5088 - The Traveling Salesman Problem: Algorithms & Optimization

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

We discuss a number of open research topics surrounding the computation of exact and approximation solutions to large-scale instances of the TSP.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

Let $G$ be an undirected graph with $m$ edges and let $\epsilon > 0$ be a constant, and consider the Metric-TSP instance induced by the shortest path metric on $G$. First, we give an algorithm that computes, in $~O(m/\epsilon^2)$ randomized time and with high probability, a $(1 + \epsilon)$-approximation for an LP relaxation of Metric-TSP which is equivalent to the Held-Karp bound [Held and Karp, 1970]. Second, we describe an algorithm that computes, in $~O(m / \epsilon^2 + n^{1.5} / \epsilon^3)$ randomized time and with high probability, a tour of $G$ with cost at most $(3 + \epsilon)/2$ times the minimum cost tour of $G$. The second algorithm uses the LP solution from the first algorithm as a starting point. (Joint work with Chandra Chekuri.)

We study the stochastic version of the k-Traveling Salesman Problem. Given a metric with independent random rewards at vertices, the objective is to minimize the expected length of a tour that collects total reward at least k. We consider both adaptive and non-adaptive solutions: an adaptive tour depends on observed rewards. We provide an $O(\log\:k)$ approximate adaptive solution and $O(\log^2\: k)$ approximate non-adaptive solution, which also upper bounds the "adaptivity gap". Time permitting, we will also discuss the setting with more general reward functions.

When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items are initially loaded in one vehicle and should be distributed before a given deadline $T$. In addition to travel time and time for deliveries, we assume that there is a fixed delay for handing over an item from one vehicle to another. We will show that it is easy to decide whether an instance is feasible, i.e., whether it is possible to deliver all items before the deadline $T$. We then consider computing a feasible tour of minimum cost, where we incur a cost per unit distance traveled by the vehicles, and a setup cost for every used vehicle. Our problem arises in practical applications and generalizes classical problems such as shallow-light trees and the bounded-latency problem. Our main result is a polynomial-time algorithm that, for any given $\alpha > 0$ and any feasible instance, computes a solution that delivers all items before time $(1+ \alpha) T$ and has cost $O(1 + 1 / \alpha)$ OPT, where OPT is the minimum cost of any feasible solution. (Joint work with Jochen Konemann and Jens Vygen. https://arxiv.org/pdf/1801.04991)

We develop polynomial-size LP-relaxations for orienteering and the regret-bounded vehicle routing problem (RVRP) and devise suitable LP-rounding algorithms that lead to various new insights and approximation results for these problems. In orienteering, the goal is to find a maximum-reward r-rooted path, possibly ending at a specified node, of length at most some given budget B. In RVRP, the goal is to find the minimum number of r-rooted paths of regret at most a given bound R that cover all nodes, where the regret of an r-v path is the difference between its length and the {distance of v from r}. For orienteering without a specified end-node, we introduce a natural bidirected LP-relaxation and obtain a simple 3-approximation algorithm via LP-rounding. This is the first LP-based guarantee for this problem. We also show that point-to-point orienteering (where the end-node is also specified) can be reduced to a regret-version of rooted orienteering at the expense of a factor-2 loss in approximation, and present an LP-relaxation with an integrality gap of 6 for this problem. For RVRP, we propose two compact LPs that lead to significant improvements, in both approximation ratio and running time, over the previous O(1)-factor approximation algorithm. One of these LPs is a rather unconventional formulation that leverages various structural properties of an RVRP-solution. (Joint work with Chaitanya Swamy.)

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We introduce a simple but useful technique called concavity of pessimistic estimators. This technique allows us to show concentration of submodular functions and concentration of matrix sums under pipage rounding (we prove the latter by a new variant of Lieb's celebrated concavity theorem in matrix analysis). A spectrally-thin tree is a spectral analog of the thin trees that played a crucial role in recent approximation algorithms for the asymmetric traveling salesman problem. Pipage rounding can be used to (constructively) obtain an $O(\kappa^{-1} \log n / \log \log n)$-spectrally thin tree, where $\kappa$ is the minimum edge conductance. (Joint work with Nick Harvey. https://arxiv.org/abs/1307.2274)

Title is TENTATIVE. Abstract: TBA.

Title is TENTATIVE. Abstract: TBA.

We study decompositions of graphs that cover small-cardinality cuts an even number of times, and we use these decompositions to design algorithms with improved approximation guarantees for the traveling salesman problem (TSP) and the 2-edge-connected spanning multigraph problem (2EC) on (restricted classes of) weighted graphs. Motivated by the well known "four-thirds conjecture", we apply our decomposition tools to the problem of uniform covers. For a cubic, 3-edge-connected graph, we show that the everywhere 18/19 vector can be efficiently written as a convex combination of tours, answering a question of Sebo. Additionally, for such graphs, we show that the everywhere 15/17 vector can be efficiently written as a convex combination of 2-edge-connected spanning multigraphs. Our constructions of these uniform covers use the algorithms of Boyd, Iwata and Takazawa for cycle covers and Cheriyan, Jordan and Ravi for tree augmentations. (Joint work with Arash Haddadan and Alantha Newman. arxiv.org/abs/1707.05387)

A classic algorithm for the traveling salesman problem (TSP) on cubic graphs consists of finding a double spanning tree on the contracted graph of a cycle cover, where a cycle cover is defined as the set of edges in the complement of a perfect matching. If a cubic graph G on n vertices has a cycle cover containing k cycles, this results in a TSP tour of size $n+2k$. Since we are interested in short TSP tours, we would like to find cycle covers that have small size, i.e., having few connected components. Moemke and Svensson showed that a bridgeless, cubic graph contains a cycle cover consisting of at most n/6 cycles. Here we show how to use a large cycle cover to obtain a small cycle cover. In particular, if G is a bipartite, cubic graph on $n$ vertices, a cycle cover of size $(1/6+\epsilon)n$ can be used to find a cycle cover of size $(1/6 - \epsilon/2)n$. If G is a bridgeless, cubic graph on $n$ vertices, a cycle cover of size $(1/6 + \epsilon)n$ that covers all 3-edge cuts in G can be used to find a cycle cover of size $(1/6 - \epsilon/5)n$. (Joint work with Arash Haddadan.)

We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time $O(n^3)$ and the other having an approximation guarantee of 7/6 and run time $O(n^{2.5})$. The 8/7 -approximation algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using “half-edges”. The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7 -approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7 -approximation. The 7/6 -approximation algorithm is similar and even simpler, and has the advantage of $\textbf{not}$ using Hartvigsen’s complicated algorithm for computing a minimum-cost triangle-free cycle cover. (Joint work with Anna Adamaszek and Matthias Mnich ICALP 2018)

What is the effectiveness of local search algorithms for TSP in the plane? Motivated by the strong results of Johnson et al. during the TSP challenge, we prove that $k$-opt yields a $(1+1/poly(k))$-approximation when points are chosen uniformly in $R^d$. We show that the randomness assumption is necessary as in the worst-case $k$-opt could return at least a 2-approximate solution.

I will present recent work by Rico Zenklusen on obtaining a 1.5-approximation for the Metric Path Traveling Salesman Problem (path TSP). All recent improvements on path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that cuts with a value strictly below 2 with respect to any Held-Karp solution form a chain. Such narrow cuts are the obstacle why Christofides' celebrated 1.5-approximation for TSP does not easily extend to the more general path version of TSP. The newly introduced approach significantly deviates from prior techniques in this point, by showing the benefit of not only focussing on narrow cuts, but instead dealing with larger s-t cuts even though they are much less structured. More precisely, we will see that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. Through this technique, we obtain a well-structured point in the Held-Karp relaxation from which we derive the 1.5-approximation. This allows us to avoid a recursive application of dynamic programming as used by Traub and Vygen in their recent (1+epsilon)-approximation, and we obtain a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. The obtained approach matches the still unbeaten 1.5-approximation guarantee of Christofides' algorithm for TSP. Hence, any further progress on the approximability of path TSP will also lead to an improvement over Christofides' 1.5-approximation for TSP.

(Joint with Jens Vygen.)

We prove new upper bounds on the integrality ratios for the standard subtour elimination LPs for the symmetric and for the asymmetric s-t-path TSP. For symmetric distances (joint work with Vera Traub), we give an improved analysis of the algorithm of Seb\H{o} and van Zuylen. For asymmetric distances (joint work with Anna K\"{o}hne and Vera Traub), we prove that the integrality ratio is constant.

TSP and subset TSP were known to have PTASes for planar and bounded genus graphs, and they were conjectured to have PTASes in minor-free graphs that contain planar and bounded genus graphs as subclasses. In this talk, we will survey existing results on designing PTASes for TSP and subset TSP, and explore the resolution of both conjectures. Demaine, Hajiaghayi and Kawarabayashi, in their seminal paper on contraction decomposition in minor-free graphs, described the first PTAS for TSP in minor-free graphs. However, their PTAS is inefficient. In a joint work with Glencora Borradaile and Christian Wulff-Nilsen, we design an efficient PTAS for TSP in minor-free graphs. This result constitutes the first part of the talk. Recently, building on the new technique developed in solving TSP problem, we are able to resolve the second conjecture, that is, designing the first PTAS for subset TSP in minor-free graphs. This is the second part of the talk. To conclude the talk, we will discuss several open problems. (One part is joint with Glencora Borradaile and Christian Wulff-Nilsen.)

Abstract: TBA

We analyze the integrality gap of a semidefinite programming relaxation of the traveling salesman problem due to de Klerk, Pasechnik, and Sotirov. We show that the integrality gap is unbounded by searching for highly structured feasible solutions; the problem of finding such solutions reduces to finding feasible solutions for a related linear program. These solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other relaxations of the traveling salesman problem. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik for the k-cycle cover problem also has an unbounded integrality gap.

We study the problem of finding a tour of n points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length of the shortest edge in the tour. The problem is known as Maximum Scatter TSP, and was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging. Arkin et al. gave a 0.5 -approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming P !=NP). Arkin et al. raised the question of whether a better approximation ratio can be obtained in the Euclidean plane. We answer this question in the affirmative in a more general setting, by giving a $(1-\epsilon)$-approximation algorithm for d-dimensional doubling metrics, with running time $\tilde{O}(n^3 + 2^{(O(K log K))} )$, where $K \leq ( 13/\epsilon)^d$. As a corollary we obtain (i) an efficient polynomial-time approximation scheme (EPTAS) for all constant dimensions d, (ii) a polynomial-time approximation scheme (PTAS) for dimension $d = (\log \log n)/c$, for a sufficiently large constant c, and (iii) a PTAS for constant d and $\epsilon = Omega(1/\log \log n)$. Furthermore, we show the dependence on d in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time. (Joint work with Laszlo Kozma, SODA 2017.)

We propose a framework for optimal $t$-matchings excluding prescribed $t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free $2$-matching, square-free $2$-matching, even factor, and arborescence problems. In this talk, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free $2$-matching algorithm, a square-free $2$-matching algorithm, and an arborescence algorithm, respectively.

The pitch of a (valid) inequality for the min knapsack polytope is the minimum integer k such that, if any k variables from its support are set to one, then the inequality is satisfied. Bounded pitch inequalities came to prominence for their connections with the Chvatal-Gomory and Bienstock-Zuckerberg operators. In this talk, we investigate the strength of bounded pitch inequalities, proving bounds on the integrality gap when they are added to the natural LP relaxation (possibly, in conjunction with other inequalities), and we discuss algorithms for approximately separating them.

A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child $i$ has for a present $j$ is of the form $p_{ij} \in \{0,p_j\}$. The only known polynomial time algorithm by Annamalai et al. gives a 12.33-approximation algorithm and is based on a modification of Haxell's hypergraph matching argument. This factor compares to the value of an exponential size \emph{configuration LP}. In this paper, we introduce a \emph{matroid} version of the Santa Claus problem with unit size presents and design an algorithm which gives a polynomial time $(3+\epsilon)$-approximation compared to a natural, compact LP. Our algorithm is also based on Haxell's augmentation tree, but despite the greater generality, it is cleaner than previous methods. Our result can then be used as a blackbox to obtain a $(6+\epsilon)$-approximation for Santa Claus (with arbitrary present sizes). This factor also compares against a natural, compact LP for Santa Claus. (Joint work with Sami Davies and Yihao Zhang.)

In the parametric global minimum cut problem, we are given a graph $G=(V,E)$ where the cost of each edge is an affine function of a parameter in $R^d$ for some fixed dimension d. Megiddo's parametric search is a widely known technique to solve parametric optimization problems. We give faster algorithms to solve two problems related to the parametric global minimum cut problem: Finding the next breakpoint in a given direction, and finding a parameter value that maximizes the global min cut value, and we show the relation between the two problems.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.