New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
From MaRDI portal
Publication:729796
DOI10.1016/j.dam.2016.07.013zbMath1358.90117OpenAlexW2183435071MaRDI QIDQ729796
Publication date: 22 December 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.07.013
global optimizationsemidefinite programmingtraveling salesman problemapproximation algorithmslinear ordering problemmax cut problemvertex ordering problemstarget visitation problem
Related Items
A semidefinite optimization approach to the target visitation problem ⋮ Block-insertion-based algorithms for the linear ordering problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A computational study and survey of methods for the single-row facility layout problem
- Semidefinite relaxations of ordering problems
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- Handbook on semidefinite, conic and polynomial optimization
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- A semidefinite optimization approach to the target visitation problem
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Induced binary probabilities and the linear ordering polytope: A status report
- A complete description of the traveling salesman polytope on 8 nodes
- The traveling salesman. Computational solutions for RSP applications
- The traveling salesman problem and its variations
- On the approximability of the traveling salesman problem
- Exact Algorithms for the Quadratic Linear Ordering Problem
- Improved Inapproximability for TSP
- A Cutting Plane Algorithm for the Linear Ordering Problem
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- On the power of unique 2-prover 1-round games
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- Approximate graph coloring by semidefinite programming
- Heuristic analysis, linear programming and branch and bound
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Optimal Weighted Ancestry Relationships
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Fixing Variables in Semidefinite Relaxations
- Reducibility among Combinatorial Problems
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Solution of a Large-Scale Traveling-Salesman Problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Geometry of cuts and metrics
