In Honour of Ted Swart

This is a tribute to my dear life-long friend, mentor and colleague Ted Swart. It includes anecdotal stories and memories of our times together, and also includes a new academic contribution in his honour, Teds polytope. Tweeks made to the Birkhoff polytope Bn endow Teds polytope Tn({\epsilon}) with a special tunable parameter {\epsilon} = {\epsilon}(n). Observe how Bn can be viewed as the convex hull of both the TSP polytope, and the set of non-tour permutation extrema, and, that its extended formulation is compact. Tours (connected 2-factor permutation matrices when viewed as adjacency matrices) can be distinguished from non-tours (disconnected 2-factor permutation matrices) where {\epsilon} scales the magnitude of tweeks made to Bn. For {\epsilon}>0, Tn({\epsilon}) is tuned so that the convex hull of extrema corresponding to transformed tours is lifted from Bn, and separated (by a hyperplane) from the convex hull of extrema corresponding to translated non-tours. This leads to creation of the feasible region of an LP model that can decide existence of a tour in a graph based on an extended formulation of the TSP polytope. That is, by designing for polynomial-time distinguishable tour extrema embedded in a subspace disjoint from non-tour extrema, NP-completeness strongholds come into play, necessarily expressed in a non-compact extended formulation of Tn({\epsilon}) i.e. a compact extended formulation of the TSP polytope cannot exist. No matter, Ted would have loved these ideas, and Tn({\epsilon}) might one day yet be useful in the study of the P versus NP conundrum. In summary, Tn({\epsilon}) is a perturbed Bn i.e. the convex hull of both an {\epsilon}-stretched TSP polytope, and the set of translated non-tour permutation extrema i.e. a TSP-like polytope and separable non-tour extrema.

• Publication year

  2023

• Venue

  arXiv.org

• Publication date

  2023-05-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2305.05011arXiv 2305.05011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Using Matching to Detect Infeasibility of Some Integer Programs

  2017cited by this paper
• Deciding Graph non-Hamiltonicity via a Closure Algorithm

  2016cited by this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cited by this paper
• The Four-Colour Theorem

  1997cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991cited by this paper
• The facets of the asymmetric 5-city traveling salesman polytope

  1989cited by this paper
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

  1986cited by this paper
• Three dimensional line stochastic matrices and extreme points

  1985cited by this paper
• An Introduction to Convex Polytopes

  1982cited by this paper
• The ellipsoid method and its consequences in combinatorial optimization

  1981cited by this paper
• The Philosophical Implications of the Four-Color Problem

  1980cited by this paper
• A systematic approach to the determination of reducible configurations in the four-color conjecture

  1978cited by this paper
• The Planar Hamiltonian Circuit Problem is NP-Complete

  1976influential reference

• No citing papers are available for this paper.