Show simple item record

dc.contributor.authorBoria, Nicolas
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2016-07-18T15:00:30Z
dc.date.available2016-07-18T15:00:30Z
dc.date.issued2013
dc.identifier.issn1793-8317
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15648
dc.language.isoenen
dc.subjectreoptimization
dc.subject.ddc003en
dc.titleReoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.isversionofjnlnameDiscrete Mathematics, Algorithms and Applications
dc.relation.isversionofjnlvol05
dc.relation.isversionofjnlissue02
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpagesn°1360004
dc.relation.isversionofdoi10.1142/S1793830913600045
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:18:29Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989
hal.identifierhal-01346332*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record