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

Beginning on Sunday, September 23 and ending Friday September 28, 2018

All times in Banff, Alberta time, MDT (UTC-6).

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) |