7 citations · 9 across the 10 of their papers we have counts for
12 papers
Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
Samuel C. Gutekunst
We study the edge-length polytope, motivated both by algorithmic research on the Circulant Traveling Salesman Problem (Circulant TSP) and number-theoretic research related to the B…
GILP: An Interactive Tool for Visualizing the Simplex Algorithm
Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys +1
The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many a…
The Two-Stripe Symmetric Circulant TSP is in P
Samuel C. Gutekunst, Billy Jin, David P. Williamson
The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of t…
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP
Samuel C. Gutekunst, David P. Williamson
Facet-defining inequalities of the symmetric Traveling Salesman Problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In th…
Mathematics of Nested Districts: The Case of Alaska
Sophia Caldera, Daryl DeFord, Moon Duchin +2
In eight states, a "nesting rule" requires that each state Senate district be exactly composed of two adjacent state House districts. In this paper we investigate the potential imp…
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Samuel C. Gutekunst, David P. Williamson
De Klerk, Pasechnik, and Sotirov give a semidefinite programming constraint for the Traveling Salesman Problem (TSP) based on the matrix-tree Theorem. This constraint says that the…
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Samuel C. Gutekunst, David P. Williamson
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a…
Root Cones and the Resonance Arrangement
Samuel C. Gutekunst, Karola Mészáros, T. Kyle Petersen
We study the connection between triangulations of a type root polytope and the resonance arrangement, a hyperplane arrangement that shows up in a surprising number of contexts.…
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of t…
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We study a semidefinite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [8] and show that their relaxation has an unbounded…
Permutation Patterns in Latin Squares
Michael J. Earnest, Samuel C. Gutekunst
In this paper we study pattern avoidance in Latin Squares, which gives us a two dimensional analogue of the well studied notion of pattern avoidance in permutations. Our main resul…
Logarithmic Representability of Integers as k-Sums
Anant P. Godbole, Samuel Gutekunst, Vince Lyzinski +1
A set A=A_{k,n} in [n]\cup{0} is said to be an additive k-basis if each element in {0,1,...,kn} can be written as a k-sum of elements of A in at least one way. Seeking multiple rep…