On residual approximation in solution extension problems

Mathias Weller (), Annie Chateau (), Rodolphe Giroudeau (), Jean-Claude König () and Valentin Pollet ()
Additional contact information
Mathias Weller: LIRMM - CNRS UMR 5506
Annie Chateau: LIRMM - CNRS UMR 5506
Rodolphe Giroudeau: LIRMM - CNRS UMR 5506
Jean-Claude König: LIRMM - CNRS UMR 5506
Valentin Pollet: LIRMM - CNRS UMR 5506

Journal of Combinatorial Optimization, 2018, vol. 36, issue 4, No 6, 1195-1220

Abstract: Abstract The solution extension variant of a problem consists in, being given an instance and a partial solution, finding the best solution comprising the given partial solution. Many problems have been studied with a similar approach. For instance the Pre-Coloring Extension problem, the clustered variant of the Travelling Salesman problem, or the General Routing Problem are in a way typical examples of solution extension variant problems. Motivated by practical applications of such variants, this work aims to explore different aspects around extension on classical optimization problems. We define residue-approximations as algorithms whose performance ratio on the non-prescribed part can be bounded, and corresponding complexity classes. Using residue-approximation, we classify problems according to their residue-approximability, exhibit distinct behaviors and give several examples and first interesting results.

Keywords: Complexity; Approximation; Extension problems; Residual approximation; TSP (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0202-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0202-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0202-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().