Optimization Online


New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

Philipp Hungerlaender (philipp.hungerlaender***at***aau.at)

Abstract: In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her relaxation seems better suited for designing polynomial-time approximation algorithms for the (LOP) than the widely-studied standard polyhedral linear relaxations. In this paper we improve the relaxation proposed by Newman and conduct a polyhedral study of the corresponding polytope. Furthermore we relate the relaxation to other linear and semidefinite relaxations for the (LOP) and for the Traveling Salesman Problem and elaborate on its connection to the Max Cut problem.

Keywords: Linear Ordering Problem; Max Cut Problem; Traveling Salesman Problem; Target Visitation Problem; Vertex Ordering Problems; Semidefinite Programming; Approximation Algorithms; Global Optimization

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: Discrete Applied Mathematics, 217(1):19 - 39, 2017.

Download: [PDF]

Entry Submitted: 01/15/2015
Entry Accepted: 01/16/2015
Entry Last Modified: 12/14/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society