12 citations · 16 across the 6 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DM2020
A New Integer Programming Formulation of the Graphical Traveling Salesman Problem
Robert D. Carr, Neil Simonetti
In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost of traveling from city to city , which is the sa…
cs.DM2020
Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs
Robert D. Carr, Arash Haddadan, Cynthia A. Phillips
We present a new algorithm, Fractional Decomposition Tree (FDT) for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial t…
cs.DS2020
Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP
Robert D. Carr, Jennifer Iglesias, Giuseppe Lanciac +1
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…