Search for: All records

The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP. 

We study the connection between triangulations of a type $A$ root polytope and the resonance arrangement, a hyperplane arrangement that shows up in a surprising number of contexts. Despite an elementary definition for the resonance arrangement, the number of resonance chambers has only been computed up to the $n=8$ dimensional case. We focus on data structures for labeling chambers, such as sign vectors and sets of alternating trees, with an aim at better understanding the structure of the resonance arrangement, and, in particular, enumerating its chambers. Along the way, we make connections with similar (and similarly difficult) enumeration questions. With the root polytope viewpoint, we relate resonance chambers to the chambers of polynomiality of the Kostant partition function. With the hyperplane viewpoint, we clarify the connections between resonance chambers and threshold functions. In particular, we show that the base-2 logarithm of the number of resonance chambers is asymptotically $n^2$.