| dc.contributor.author | Boria, Nicolas | |
| dc.contributor.author | Monnot, Jérôme | |
| dc.contributor.author | Paschos, Vangelis | |
| dc.date.accessioned | 2016-07-18T15:00:30Z | |
| dc.date.available | 2016-07-18T15:00:30Z | |
| dc.date.issued | 2013 | |
| dc.identifier.issn | 1793-8317 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/15648 | |
| dc.language.iso | en | en |
| dc.subject | reoptimization | |
| dc.subject.ddc | 003 | en |
| dc.title | Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph | |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | 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. | |
| dc.relation.isversionofjnlname | Discrete Mathematics, Algorithms and Applications | |
| dc.relation.isversionofjnlvol | 05 | |
| dc.relation.isversionofjnlissue | 02 | |
| dc.relation.isversionofjnldate | 2013 | |
| dc.relation.isversionofjnlpages | n°1360004 | |
| dc.relation.isversionofdoi | 10.1142/S1793830913600045 | |
| dc.subject.ddclabel | Recherche opérationnelle | en |
| dc.relation.forthcoming | non | en |
| dc.relation.forthcomingprint | non | en |
| dc.description.ssrncandidate | non | |
| dc.description.halcandidate | oui | |
| dc.description.readership | recherche | |
| dc.description.audience | International | |
| dc.relation.Isversionofjnlpeerreviewed | oui | |
| dc.date.updated | 2017-02-21T08:18:29Z | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 989 | |
| hal.identifier | hal-01346332 | * |
