
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érenceDate
2012Conference title
6th International Workshop on Algorithm and Computation, WALCOM 2012Conference date
2012-02Conference city
DhakaConference country
BangladeshBook title
WALCOM: Algorithm and Computation 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. ProceedingsBook author
Rahman, Md. SaidurPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-28075-7
Pages
76-87
Metadata
Show full item recordAuthor(s)
Boria, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

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
ReoptimizationRelated items
Showing items related by title and author.
-
Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2013) Article accepté pour publication ou publié
-
Boria, Nicolas; Paschos, Vangelis; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Boria, Nicolas; Gourvès, Laurent; Paschos, Vangelis; Monnot, Jérôme (2021) Communication / Conférence
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003) Article accepté pour publication ou publié
-
Boria, Nicolas; Paschos, Vangelis (2010) Article accepté pour publication ou publié