Showing 1–1 of 1 results for author: Lanciac, G

Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP

Authors: Robert D. Carr, Jennifer Iglesias, Giuseppe Lanciac, Benjamin Moseley

Abstract: We introduce multiple symmetric LP relaxations for minimum cut problems. The relaxations give optimal and approximate solutions when the input is a Hamiltonian cycle. We show that this leads to one of two interesting results. In one case, these LPs always give optimal and near optimal solutions, and then they would be the smallest known symmetric LPs for the problems considered. Otherwise, these L… ▽ More We introduce multiple symmetric LP relaxations for minimum cut problems. The relaxations give optimal and approximate solutions when the input is a Hamiltonian cycle. We show that this leads to one of two interesting results. In one case, these LPs always give optimal and near optimal solutions, and then they would be the smallest known symmetric LPs for the problems considered. Otherwise, these LP formulations give strictly better LP relaxations for the traveling salesperson problem than the subtour relaxation. We have the smallest known LP formulation that is a 9/8-approximation or better for min-cut. In addition, the LP relaxation of min-cut investigated in this paper has interesting constraints; the LP contains only a single typical min-cut constraint and all other constraints are typically only used for max-cut relaxations. △ Less

Submitted 24 May, 2020; originally announced May 2020.

Comments: Submitted to a journal

MSC Class: 68R10 ACM Class: G.2.2