New semidefinite programming relaxations for the Linear Ordering and the Traveling Salesman Problem

详细信息    查看全文

• 作者：Philipp Hungerlä ; nder ^{philipp.hungerlaender@aau.at}
• 关键词：Linear Ordering Problem ; Max cut problem ; Traveling Salesman Problem ; Target visitation problem ; Vertex ordering problems ; Semidefinite programming ; Approximation algorithms ; Global optimization
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P1
• 页码：19-39
• 全文大小：624 K
• 卷排序：217

文摘

In 2004 Newman [43] 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 (Goemans and Williamson, 1995). Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman (2004) [43] 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 strengthen the relaxation proposed by Newman (2004) [43] 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.