David P. Williamson
Home
Posts
Publications
Talks
Courses
Contact
CV
Talks
2023
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
Sep 20, 2023 10:30 AM — 11:00 AM
Banff International Research Station for Mathematical Innovation and Discovery, Banff, Canada
PDF
Slides
Video
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
May 5, 2023 1:30 PM
Columbia School of Business, Columbia University, New York, NY, USA
Slides
2021
The Two Stripe Symmetric Circulant TSP is in P
Nov 10, 2021 10:00 AM
Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach, Germany
PDF
Slides
2020
Semidefinite Programming Relaxations of the Traveling Salesman Problem
Dec 4, 2020 3:30 PM
Center for Applied Mathematics, Cornell University, Ithaca, NY
PDF
Slides
Semidefinite Programming Relaxations for the Traveling Salesman Problem
Oct 23, 2020 3:30 PM
University of Waterloo, Waterloo, Canada
PDF
Slides
2019
Tight Bounds for Online Weighted Tree Augmentation
Jun 3, 2019 2:50 PM
Simons Institute for the Theory of Computing, Berkeley, CA, USA
PDF
Slides
2018
Semidefinite Programming Relaxations of the Traveling Salesman Problem
Oct 24, 2018 2:30 PM
University of Massachusetts Amherst, Amherst, MA, USA
Slides
Vector Representations of Graphs and the Maximum Cut Problem
Feb 27, 2018 12:00 AM
University of California at Berkeley, Berkeley, CA, USA
The Subtour LP for the Traveling Salesman Problem
Jan 24, 2018 12:00 AM
Google. Mountain View, CA, USA
Slides
Video
2016
The Subtour LP for the Traveling Salesman Problem
Apr 21, 2016 12:00 AM
University of Illinois at Urbana-Champaign. Champaign, IL, USA
Slides
A Simple 3/4-Approximation Algorithm for the Maximum Satisfiability Problem
Apr 1, 2016 12:00 AM
University of Pennsylvania, Philadelphia, PA, USA
PDF
Slides
2015
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
Sep 17, 2015 12:00 AM
Cargesè, Corscia, France
PDF
Slides
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
Jul 14, 2015 12:00 AM
Pittsburgh, PA, USA
PDF
Slides
The Subtour LP for the Traveling Salesman Problem
Apr 8, 2015 12:00 AM
University of Michigan, Ann Arbor, MI, USA
PDF
Slides
2014
A Simple, Greedy Approximation Algorithm for MAX SAT
Sep 20, 2014 9:45 AM
Rutgers University, Piscataway, NJ, USA
PDF
Slides
The Traveling Salesman Problem: An Overview
Jan 21, 2014 12:00 AM
Ebay Research, San Jose, CA, USA
PDF
Slides
2012
The Rank Aggregation Problem
Dec 10, 2012 12:00 AM
Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
PDF
Slides
A 3/2-Approximation Algorithm for Some Minimum-Cost Graph Problems
Aug 23, 2012 12:00 AM
Berlin, Germany
PDF
Slides
The Subtour LP for the Traveling Salesman Problem
Jun 18, 2012 12:00 AM
Universität Wien. Vienna, Austria.
PDF
Slides
The Subtour LP for the Traveling Salesman Problem
Mar 6, 2012 12:00 AM
Hanoi, Vietnam
PDF
Slides
What Computer Can Compute (Approximately)
Jan 6, 2012 12:00 AM
University of Hawaii Department of Mathematics. Honolulu, HI, USA
2011
The Subtour LP for the Traveling Salesman Problem
Nov 22, 2011 12:00 AM — 6:28 PM
Cornell University, Ithaca, NY, USA
PDF
Slides
The Subtour LP for the Traveling Salesman Problem
Oct 12, 2011 12:00 AM
Georgia Institute of Technology, Atlanta, GA, USA
Slides
Some Open Problems in Approximationm Algorithms
Aug 18, 2011 11:15 AM — 6:32 PM
Princeton, NJ, USA
PDF
Slides
What Computers Can Compute (Approximately)
Jun 11, 2011 12:00 AM
TU Chemnitz, Chemnitz, Germany
PDF
Slides
The Subtour LP for the Traveling Salesman Problem
May 30, 2011 12:00 AM
TU Berlin, Berlin, Germany
An Experimental Evaluation of Incremental and Hierarchical $k$-Median Algorithms
May 6, 2011 12:00 AM
Chania, Greece
PDF
Slides
Some Open Problems in Approximation Algorithms
Feb 28, 2011 12:00 AM
University of Bonn, Bonn, Germany
PDF
Slides
What Computers Can Compute (Approximately)
Feb 11, 2011 12:00 AM
Berlin Mathematical School. Berlin, Germany
PDF
Slides
Cite
×