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

Achatz, 2006, Der corruption perceptions index und das linear ordering problem, ORNews, 26, 10 2012 Applegate, 2006 Boenchendorf, 1982, vol. 74 Boyd, 2004 Buchheim, 2010, Exact algorithms for the quadratic linear ordering problem, INFORMS J. Comput., 22, 168, 10.1287/ijoc.1090.0318 Chimani, 2013, Exact approaches to multilevel vertical orderings, INFORMS J. Comput., 25, 611, 10.1287/ijoc.1120.0525 Christof, 1991, A complete description of the traveling salesman polytope on 8 nodes, Oper. Res. Lett., 10, 497, 10.1016/0167-6377(91)90067-Y Christofides, 1976 Cook, 2011 Cvetković, 1999, Semidefinite programming methods for the symmetric traveling salesman problem, 126 Dantzig, 1954, Solution of a large scale traveling salesman problem, J. Oper. Res. Soc. Am., 2, 393 de Klerk, 2008, On semidefinite programming relaxations of the traveling salesman problem, SIAM J. Optim., 19, 1559, 10.1137/070711141 de Klerk, 2012, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, Math. Program., 133, 75, 10.1007/s10107-010-0411-5 Deza, 1997, vol. 15 U. Feige, M.X. Goemans, Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182–189. Fischer, 2013 Fishburn, 1992, Induced binary probabilities and the linear ordering polytope: a status report, Math. Social Sci., 23, 67, 10.1016/0165-4896(92)90038-7 Frieze, 1997, Improved approximation algorithms for MAXk-CUT and MAX BISECTION, Algorithmica, 18, 67, 10.1007/BF02523688 Garey, 1974, Some simplified np-complete problems, 47 Glover, 1974, Optimal weighted ancestry relationships, Manage. Sci., 20, 1190, 10.1287/mnsc.20.8.1190 Goemans, 2000, Combinatorial optimization Goemans, 1995, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115, 10.1145/227683.227684 Grötschel, 1984, A cutting plane algorithm for the linear ordering problem, Oper. Res., 32, 1195, 10.1287/opre.32.6.1195 D. Grundel, D. Jeffcoat, Formulation and solution of the target visitation problem, in: Proceedings of the AIAA 1st Intelligent Systems Technical Conference, 2004. Gutin, 2002 Halperin, 2002, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Struct. Algorithms, 20, 382, 10.1002/rsa.10035 Held, 1970, The traveling salesman problem and minimum spanning trees, Oper. Res., 18, 1138, 10.1287/opre.18.6.1138 Helmberg, 2000, Fixing variables in semidefinite relaxations, SIAM J. Matrix Anal. Appl., 21, 952, 10.1137/S089547989631442X A. Hildenbrandt, O. Heismann, G. Reinelt, The target visitation problem, in: Presentation held at the 18th Combinatorial Optimization Workshop in Aussois on January 09, 2014. A. Hildenbrandt, G. Reinelt, O. Heismann, Integer programming models for the target visitation problem, in: Proceedings of the 16th International Multiconference of the Information Society, Vol. A, 2013, pp. 569–572. Hungerländer, 2014, A semidefinite optimization approach to the target visitation problem, Optim. Lett. Hungerländer, 2013, A computational study and survey of methods for the single-row facility layout problem, Comput. Optim. Appl., 55, 1, 10.1007/s10589-012-9505-8 Hungerländer, 2013, Semidefinite relaxations of ordering problems, Math. Program., 140, 77, 10.1007/s10107-012-0627-7 Jünger, 1997, 2-layer straightline crossing minimization: performance of exact and heuristic algorithms, J. Graph Algorithms Appl., 1, 1, 10.7155/jgaa.00001 Karger, 1998, Approximate graph coloring by semidefinite programming, J. ACM, 45, 246, 10.1145/274787.274791 Karp, 1972, Reducibility among combinatorial problems, 85 S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC’02, 2002, pp. 767–775. Lampis, 2012, Improved inapproximability for tsp, vol. 7408, 243 Leontief, 1936, Quantitative input–output relations in the economic system of the united states, Rev. Econ. Stat., 18, 105, 10.2307/1927837 Lovász, 1991, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim., 1, 166, 10.1137/0801013 Martí, 2011 Newman, 2004, Cuts and orderings: On semidefinite relaxations for the linear ordering problem, vol. 3122, 195 Newman, 2004 Newman, 2001, Fences are futile: On relaxations for the linear ordering problem, 333 Padberg, 1991, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 60, 10.1137/1033004 Papadimitriou, 2006, On the approximability of the traveling salesman problem, Combinatorica, 26, 101, 10.1007/s00493-006-0008-z Reinelt, 1994 Shmoys, 1990, Analyzing the held-karp tsp bound: A monotonicity property with application, Inform. Process. Lett., 35, 281, 10.1016/0020-0190(90)90028-V Slater, 1961, Inconsistencies in a schedule of paired comparisons, Biometrika, 48, 303, 10.1093/biomet/48.3-4.303 Sturm, 1999, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11–12, 625, 10.1080/10556789908805766 Tucker, 1960 2000 Wolsey, 1980, Heuristic analysis, linear programming and branch and bound, Math. Program. Stud., 13, 121, 10.1007/BFb0120913 Younger, 1963, Minimum feedback arc sets for a directed graph, IEEE Trans. Circuit Theory, 10, 238, 10.1109/TCT.1963.1082116