David P. Williamson
Home
Posts
Publications
Talks
Courses
Contact
CV
Traveling Salesman Problem
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP
The Two-Stripe Symmetric Circulant TSP is in P
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
Prize-Collecting TSP with a Budget Constraint
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
»
Cite
×