• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph

Thumbnail
Date
2013
Dewey
Recherche opérationnelle
Sujet
reoptimization
Journal issue
Discrete Mathematics, Algorithms and Applications
Volume
05
Number
02
Publication date
2013
Article pages
n°1360004
DOI
http://dx.doi.org/10.1142/S1793830913600045
URI
https://basepub.dauphine.fr/handle/123456789/15648
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Boria, Nicolas
Monnot, Jérôme
Paschos, Vangelis
Type
Article accepté pour publication ou publié
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 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 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. We use this setting to study weighted versions of MAX Pk-FREE SUBGRAPH and MAX PLANAR SUBGRAPH, which are representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. We also show that the techniques presented allow us to handle BIN PACKING.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.