Improving on best-of-many-Christofides for \(T\)-tours (Q2661569): Difference between revisions

@@ Property / DOI @@
-.1016/j.orl.2020.09.009
@@ Property / DOI: 10.1016/j.orl.2020.09.009 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3090361369
@@ Property / OpenAlex ID: W3090361369 / rank @@
+Normal rank
@@ Property / cites work @@
+Improving Christofides' Algorithm for the s-t Path TSP
+Normal rank
@@ Property / cites work @@
+A construction for binary matroids
@@ Property / cites work: A construction for binary matroids / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating minimum-cost connected \(T\)-joins
@@ Property / cites work: Approximating minimum-cost connected \(T\)-joins / rank @@
+Normal rank
@@ Property / cites work @@
+Matching, Euler tours and the Chinese postman
@@ Property / cites work: Matching, Euler tours and the Chinese postman / rank @@
+Normal rank
@@ Property / cites work @@
+Better \(s-t\)-tours by Gao trees
@@ Property / cites work: Better \(s-t\)-tours by Gao trees / rank @@
+Normal rank
@@ Property / cites work @@
+Analysis of Christofides' heuristic: some paths are more difficult than cycles
+Normal rank
@@ Property / cites work @@
+Minimum cuts in near-linear time
@@ Property / cites work: Minimum cuts in near-linear time / rank @@
+Normal rank
@@ Property / cites work @@
+A new approach to the minimum cut problem
@@ Property / cites work: A new approach to the minimum cut problem / rank @@
+Normal rank
@@ Property / cites work @@
+Computing All Small Cuts in an Undirected Network
@@ Property / cites work: Computing All Small Cuts in an Undirected Network / rank @@
+Normal rank
@@ Property / cites work @@
+Layers and matroids for the traveling salesman's paths
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+Eight-Fifth Approximation for the Path TSP
@@ Property / cites work: Eight-Fifth Approximation for the Path TSP / rank @@
+Normal rank
@@ Property / cites work @@
+Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
+Normal rank
@@ Property / cites work @@
+The Salesman’s Improved Paths through Forests
@@ Property / cites work: The Salesman’s Improved Paths through Forests / rank @@
+Normal rank
@@ Property / cites work @@
+Q3931037
@@ Property / cites work: Q3931037 / rank @@
+Normal rank
@@ Property / cites work @@
+Approaching 3/2 for the             <i>s</i>             -             <i>t</i>             -path TSP
+Normal rank
@@ Property / cites work @@
+An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
+Normal rank
@@ Property / cites work @@
+Reducing path TSP to TSP
@@ Property / cites work: Reducing path TSP to TSP / rank @@
+Normal rank
@@ Property / cites work @@
+Suboptimal cuts: Their enumeration, weight and number
+Normal rank
@@ Property / cites work @@
+Reassembling Trees for the Traveling Salesman
@@ Property / cites work: Reassembling Trees for the Traveling Salesman / rank @@
+Normal rank
@@ Property / cites work @@
+Heuristic analysis, linear programming and branch and bound
+Normal rank
@@ Property / cites work @@
+A 1.5-Approximation for Path TSP
@@ Property / cites work: A 1.5-Approximation for Path TSP / rank @@
+Normal rank
@@ Property / cites work @@
+Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
+Normal rank
@@ Property / DOI @@
+.1016/J.ORL.2020.09.009
@@ Property / DOI: 10.1016/J.ORL.2020.09.009 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2661569