Thumbnail

Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion

Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2012), Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion, dans Rahman, Md. Saidur, WALCOM: Algorithm and Computation 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings, Springer : Berlin Heidelberg, p. 76-87

Voir/Ouvrir
Type
Communication / Conférence
Date
2012
Titre du colloque
6th International Workshop on Algorithm and Computation, WALCOM 2012
Date du colloque
2012-02
Ville du colloque
Dhaka
Pays du colloque
Bangladesh
Titre de l'ouvrage
WALCOM: Algorithm and Computation 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings
Auteurs de l’ouvrage
Rahman, Md. Saidur
Éditeur
Springer
Ville d’édition
Berlin Heidelberg
Isbn
978-3-642-28075-7
Pages
76-87
Métadonnées
Afficher la notice complète
Auteur(s)
Boria, Nicolas cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I′ resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT in order to solve Π in I′, either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. In this setting we study the weighted version of max weighted P k -free subgraph. We then show, how the technique we use allows us to handle also bin packing.
Mots-clés
Reoptimization