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, in 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

View/Open
Type
Communication / Conférence
Date
2012
Conference title
6th International Workshop on Algorithm and Computation, WALCOM 2012
Conference date
2012-02
Conference city
Dhaka
Conference country
Bangladesh
Book title
WALCOM: Algorithm and Computation 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings
Book author
Rahman, Md. Saidur
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-28075-7
Pages
76-87
Metadata
Show full item record
Author(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]
Abstract (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.
Subjects / Keywords
Reoptimization