Show simple item record

Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2012-06-26T13:54:33Z
dc.date.available2012-06-26T13:54:33Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9587
dc.language.isoenen
dc.subjectReoptimization
dc.subject.ddc003en
dc.titleReoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
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 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.
dc.identifier.citationpages76-87
dc.relation.ispartoftitleWALCOM: Algorithm and Computation 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings
dc.relation.ispartofeditorRahman, Md. Saidur
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2012
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-28075-7
dc.relation.conftitle6th International Workshop on Algorithm and Computation, WALCOM 2012
dc.relation.confdate2012-02
dc.relation.confcityDhaka
dc.relation.confcountryBangladesh
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:23:05Z
hal.identifierhal-01508825*
hal.version1*
hal.update.actionupdateMetadata*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
mpkfs-lncs-12final.pdf
Size:
190.4Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record