Publikation: New semidefinite programming relaxation...
Stammdaten
Titel: | New semidefinite programming relaxations for the Linear Ordering and the Traveling Salesman Problem |
Untertitel: | (Online-Publikation und Preprint*) |
Kurzfassung: | AbstractIn 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. *Prepint verfügbar unter : http://www.optimization-online.org/DB_HTML/2015/01/4743.html |
Schlagworte: |
Publikationstyp: | Beitrag in Zeitschrift (Autorenschaft) |
Erscheinungsdatum: | 03.08.2016 (Online) |
Erschienen in: |
Discrete Applied Mathematics
Discrete Applied Mathematics
(
Elsevier SCI Ltd;
. Boros
)
zur Publikation |
Titel der Serie: | Combinatorial Optimization: Theory, Computation, and Applications |
Bandnummer: | 217 |
Heftnummer: | - |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 19 - 39 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 03.08.2016 |
ISBN (e-book): | - |
eISSN: | 0166-218X |
DOI: | - |
Homepage: | http://www.sciencedirect.com/science/article/pii/S0166218X1630333X |
Open Access |
|
AutorInnen
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Zitationsindex |
Informationen zum Zitationsindex: Master Journal List
|
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: | Keine verknüpften Projekte vorhanden |
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: | Keine verknüpften Veranstaltung vorhanden |
Vorträge: | Keine verknüpften Vorträge vorhanden |