New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
type: Item
instance of: scholarly article
title: New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
zbMATH Open document ID: 1358.90117
author: Philipp Hungerländer
published in: Discrete Applied Mathematics
publication date: 2016-12-22T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6668148
zbMATH Keywords: linear ordering problem
zbMATH Keywords: max cut problem
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: target visitation problem
zbMATH Keywords: vertex ordering problems
zbMATH Keywords: semidefinite programming
zbMATH Keywords: approximation algorithms
zbMATH Keywords: global optimization
describes a project that uses: TSPLIB
describes a project that uses: Concorde
describes a project that uses: SeDuMi
MaRDI profile type: Publication
full work available at URL: j.dam.2016.07.013
OpenAlex ID: W2183435071
cites work: Handbook on semidefinite, conic and polynomial optimization
cites work: Q3425132
cites work: Q3320091
cites work: Q4821526
cites work: Exact algorithms for the quadratic linear ordering problem
cites work: A complete description of the traveling salesman polytope on 8 nodes
cites work: Q4263707
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: On Semidefinite Programming Relaxations of the Traveling Salesman Problem
cites work: Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
cites work: Geometry of cuts and metrics
cites work: Induced binary probabilities and the linear ordering polytope: A status report
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Optimal Weighted Ancestry Relationships
cites work: Q4517107
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: The traveling salesman problem and its variations
cites work: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: Fixing Variables in Semidefinite Relaxations
cites work: A semidefinite optimization approach to the target visitation problem
cites work: A computational study and survey of methods for the single-row facility layout problem
cites work: Semidefinite relaxations of ordering problems
cites work: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
cites work: Approximate graph coloring by semidefinite programming
cites work: Reducibility among Combinatorial Problems
cites work: On the power of unique 2-prover 1-round games
cites work: Improved Inapproximability for TSP
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Q4537753
cites work: A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
cites work: On the approximability of the traveling salesman problem
cites work: The traveling salesman. Computational solutions for RSP applications
cites work: Analyzing the Held-Karp TSP bound: A monotonicity property with application
cites work: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
cites work: Heuristic analysis, linear programming and branch and bound
DOI: 10.1016/J.DAM.2016.07.013
description: scientific article; zbMATH DE number 6668148