Show simple item record

dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2011-11-03T18:31:44Z
dc.date.available2011-11-03T18:31:44Z
dc.date.issued2013
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/7388
dc.language.isoenen
dc.subjectreoptimization
dc.subject.ddc003en
dc.titleReoptimization of maximum weight induced hereditary subgraph problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe reoptimization issue studied in this paper can be described as follows: given aninstance I of some problem Π, an optimal solution O P T for Π in I and an instance I ′ resultingfrom a local perturbation of I that consists of insertions or removals of a small number ofdata, we wish to use O P T in order to solve Π in I ′, either optimally or by guaranteeingan approximation ratio better than that guaranteed by an ex nihilo computation and withrunning time better that that needed for such a computation. We use this setting in order tostudy weighted versions of several representatives of a broad class of problems known in theliterature as maximum induced hereditary subgraph problems. The main problems studiedare max independent set, max k -colorable subgraph, max Pk-free subgraph, maxsplit subgraph and max planar subgraph. We also show, how the techniques presentedallow us to handle also bin packing.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol514
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages61-74
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2012.10.037
dc.relation.isversionofbktitle61-74
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:19:08Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record