On Residual Approximation in Solution Extension Problems

Mathias Weller 1, 2 Annie Château 1, 2 Rodolphe Giroudeau 3 Jean-Claude König 3 Valentin Pollet 3
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2018, 36 (4), pp.1195-1220. 〈10.1007/s10878-017-0202-5〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01889394
Contributeur : Rodolphe Giroudeau <>
Soumis le : samedi 6 octobre 2018 - 13:54:50
Dernière modification le : lundi 11 février 2019 - 11:50:15

Identifiants

Collections

Citation

Mathias Weller, Annie Château, Rodolphe Giroudeau, Jean-Claude König, Valentin Pollet. On Residual Approximation in Solution Extension Problems. Journal of Combinatorial Optimization, Springer Verlag, 2018, 36 (4), pp.1195-1220. 〈10.1007/s10878-017-0202-5〉. 〈lirmm-01889394〉

Partager

Métriques

Consultations de la notice

36