The Traveling Salesman Problem: Algorithms & Optimization

Videos from BIRS Workshop 18w5088

, Ecole Polytechnique Federale de Lausanne
- 10:20
A constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem
Watch video | Download video: 201809240901-Tarnawski.mp4 (271M)
, University of Waterloo
- 11:53
Open problems on TSP computation
Watch video | Download video: 201809241048-Cook.mp4 (231M)
, Univ. Illinois at Urbana-Champaign
- 16:03
Approximating metric TSP and approximating the Held-Karp LP
Watch video | Download video: 201809241533-Quanrud.mp4 (106M)
, University of Michigan
- 16:33
Stochastic k-TSP
Watch video | Download video: 201809241604-Nagarajan.mp4 (95M)
, University of Bonn
- 17:08
Vehicle routing with subtours
Watch video | Download video: 201809241634-Held.mp4 (109M)
, University of Alberta
- 17:39
Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
Watch video | Download video: 201809241709-Friggstad.mp4 (108M)
, Vrije Universiteit Amsterdam
- 09:34
Pipage rounding, pessimistic estimators and matrix concentration
Watch video | Download video: 201809250902-Olver.mp4 (106M)
, University of Washington
- 10:44
Thin trees and the asymmetric traveling salesman, Part 1
Watch video | Download video: 201809250934-OveisGharan.mp4 (273M)
, Stanford University
- 11:58
Thin trees and the asymmetric traveling salesman, Part 2
Watch video | Download video: 201809251106-Anari.mp4 (187M)
, Carnegie Mellon University
- 16:07
Shorter tours and longer detours
Watch video | Download video: 201809251535-Ravi.mp4 (116M)
, CNRS and Université Grenoble-Alpes
- 16:31
Using large cycle covers to find small cycle covers in cubic graphs
Watch video | Download video: 201809251608-Newman.mp4 (112M)
, CNRS & Sorbonne Université
- 17:36
On the effectiveness of k-opt for Euclidean TSP
Watch video | Download video: 201809251715-Cohen-Addad.mp4 (84M)
, ETH
- 10:01
A 1.5-approximation for path TSP
Watch video | Download video: 201809260903-Naegele.mp4 (161M)
, University of Bonn
- 11:27
Beating the integrality ratio for s-t-tours in graphs
Watch video | Download video: 201809261029-Traub.mp4 (240M)
, University of Bonn
- 12:32
Integrality ratios for the s-t-path TSP
Watch video | Download video: 201809261130-Vygen.mp4 (269M)
, Oregon State University
- 09:36
PTASes for (subset) TSP in minor-free graphs
Watch video | Download video: 201809270903-Le.mp4 (200M)
, CNRS & INP Grenoble
- 11:40
The salesman, the postman and (delta-) matroids
Watch video | Download video: 201809271030-Sebo.mp4 (302M)
, Cornell University
- 16:01
Semidefinite programming relaxations of the Traveling Salesman Problem
Watch video | Download video: 201809271534-Gutekunst.mp4 (90M)
, University of Bremen and Saarland University
- 16:27
Maximum Scatter TSP in Doubling Metrics
Watch video | Download video: 201809271602-Moemke.mp4 (96M)
, Hosei University
- 16:59
Excluded t-factors in bipartite graphs: A unified framework for nonbipartite matchings and restricted 2-matchings
Watch video | Download video: 201809271628-Takazawa.mp4 (93M)
, Columbia University
- 17:31
Bounded pitch inequalities for min knapsack: approximate separation and integrality gaps
Watch video | Download video: 201809271701-Faenza.mp4 (110M)
, University of Washington
- 09:38
A Tale of Santa Claus, Hypergraphs and Matroids
Watch video | Download video: 201809280905-Rothvoss.mp4 (108M)
, University of British Columbia
- 10:05
Strongly Polynomial Algorithms for Some Problems Related to Parametric Global Minimum Cuts
Watch video | Download video: 201809280939-McCormick.mp4 (105M)