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

Arriving in Banff, Alberta on Sunday, September 23 and departing Friday September 28, 2018
Sunday, September 23
16:00 - 17:30 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre)
17:30 - 19:30 Dinner
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.
(Vistas Dining Room)
20:00 - 22:00 Informal gathering (Corbett Hall Lounge (CH 2110))
Monday, September 24
07:00 - 08:45 Breakfast
Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
08:45 - 09:00 Introduction and Welcome by BIRS Staff
A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.
(TCPL 201)
09:00 - 10:15 Jakub Tarnawski: A constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem (TCPL 201)
10:15 - 10:45 Coffee Break (TCPL Foyer)
10:45 - 11:45 Bill Cook: Open problems on TSP computation
We discuss a number of open research topics surrounding the computation of exact and approximation solutions to large-scale instances of the TSP.
(TCPL 201)
11:45 - 13:00 Lunch
Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
13:00 - 14:00 Guided Tour of The Banff Centre
Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.
(Corbett Hall Lounge (CH 2110))
14:00 - 14:20 Group Photo
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!
(TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 16:00 Kent Quanrud: Approximating metric TSP and approximating the Held-Karp LP
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.)
(TCPL 201)
16:00 - 16:30 Viswanath Nagarajan: Stochastic k-TSP
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.
(TCPL 201)
16:30 - 17:00 Stephan Held: Vehicle routing with subtours
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)
(TCPL 201)
17:00 - 17:30 Zachary Friggstad: Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
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.)
(TCPL 201)
17:30 - 19:30 Dinner
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.
(Vistas Dining Room)
Tuesday, September 25
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:30 Neil Olver: Pipage rounding, pessimistic estimators and matrix concentration
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)
(TCPL 201)
09:30 - 10:30 Shayan Oveis Gharan: Thin trees and the asymmetric traveling salesman, Part 1
Title is TENTATIVE. Abstract: TBA.
(TCPL 201)
10:30 - 11:00 Coffee Break (TCPL Foyer)
11:00 - 12:00 Nima Anari: Thin trees and the asymmetric traveling salesman, Part 2
Title is TENTATIVE. Abstract: TBA.
(TCPL 201)
12:00 - 13:30 Lunch (Vistas Dining Room)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 16:00 R. Ravi: Shorter tours and longer detours
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)
(TCPL 201)
16:00 - 16:30 Alantha Newman: Using large cycle covers to find small cycle covers in cubic graphs
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.)
(TCPL 201)
16:30 - 17:00 Katarzyna Paluch: New approximation algorithms for (1,2)-TSP
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)
(TCPL 201)
17:00 - 17:30 Vincent Cohen-Addad: On the effectiveness of k-opt for Euclidean TSP
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.
(TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Wednesday, September 26
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Martin Naegele: A 1.5-approximation for path TSP
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Vera Traub: Beating the integrality ratio for s-t-tours in graphs
(Joint with Jens Vygen.)
(TCPL 201)
11:30 - 12:30 Jens Vygen: Integrality ratios for the s-t-path TSP
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.
(TCPL 201)
12:30 - 13:30 Lunch (Vistas Dining Room)
13:30 - 17:30 Free Afternoon (Banff National Park)
17:30 - 19:30 Dinner (Vistas Dining Room)
Thursday, September 27
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Hung Le: PTASes for (subset) TSP in minor-free graphs
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.)
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Andras Sebo: The salesman, the postman and (delta-) matroids
Abstract: TBA
(TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 16:00 Sam Gutekunst: Semidefinite programming relaxations of the Traveling Salesman Problem
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.
(TCPL 201)
16:00 - 16:30 Tobias Moemke: Maximum Scatter TSP in Doubling Metrics
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.)
(TCPL 201)
16:30 - 17:00 Kenjiro Takazawa: Excluded t-factors in bipartite graphs: A unified framework for nonbipartite matchings and restricted 2-matchings
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.
(TCPL 201)
17:00 - 17:30 Yuri Faenza: Bounded pitch inequalities for min knapsack: approximate separation and integrality gaps
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.
(TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Friday, September 28
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:30 Thomas Rothvoss: A Tale of Santa Claus, Hypergraphs and Matroids
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.)
(TCPL 201)
09:30 - 10:00 Tom McCormick: Strongly Polynomial Algorithms for Some Problems Related to Parametric Global Minimum Cuts
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
11:15 - 12:00 Checkout by Noon
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.
(Front Desk - Professional Development Centre)
11:30 - 13:30 Lunch from 11:30 to 13:30 (Vistas Dining Room)