On residual approximation in solution extension problems

DOI10.1007/s10878-017-0202-5zbMath1412.90132OpenAlexW2767442395MaRDI QIDQ1631675

Mathias Weller, Rodolphe Giroudeau, Annie Chateau, Valentin Pollet, Jean-Claude Konig

Publication date: 6 December 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0202-5

zbMATH Keywords

TSPcomplexityapproximationextension problemsresidual approximation

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (2)

Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ On the approximation hardness of geodetic set and its variants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Improved approximations for TSP with simple precedence constraints
• A bounded approximation for the minimum cost 2-sat problem
• An approximation algorithm for the general routing problem
• Precoloring extension. I: Interval graphs
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Which problems have strongly exponential complexity?
• Approximating MIN 2-SAT and MIN 3-SAT
• Shortest paths algorithms: Theory and experimental evaluation
• Better approximation algorithms for the maximum internal spanning tree problem
• Precoloring extension on unit interval graphs
• On Residual Approximation in Solution Extension Problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
• 8/7-approximation algorithm for (1,2)-TSP
• A linear-time approximation algorithm for the weighted vertex cover problem
• On the Computational Complexity of Combinatorial Problems
• P-Complete Approximation Problems
• A fundamental problem in vehicle routing
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Restricted delivery problems on a network
• An Approximation Algorithm for the Traveling Salesman Problem with Backhauls
• The Traveling Salesman Problem with Distances One and Two
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Combinatorial optimization. Theory and algorithms.
• On the complexity of \(k\)-SAT

This page was built for publication: On residual approximation in solution extension problems