Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorToubaline, Sónia*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2014-02-18T16:21:19Z
dc.date.available2014-02-18T16:21:19Z
dc.date.issued2013
dc.identifier.issn0167-6377
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12689
dc.language.isoenen
dc.subjectAssignment problem
dc.subjectApproximation
dc.subjectComplexity
dc.subjectExact algorithm
dc.subjectMin edge blocker
dc.subjectMost vital edges
dc.subject.ddc003en
dc.titleCritical edges for the assignment problem : complexity and exact resolution
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of security and crime Science, University College London;Royaume-Uni
dc.description.abstractenThis paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with nn vertices on each part and with costs on its edges, kkMost Vital Edges Assignment consists of determining a set of kk edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that kkMost Vital Edges Assignment is NPNP-hard to approximate within a factor c<2c<2 and Min Edge Blocker Assignment is NPNP-hard to approximate within a factor 1.361.36. We also provide an exact algorithm for kkMost Vital Edges Assignment that runs in O(nk+2)O(nk+2). This algorithm can also be used to solve exactly Min Edge Blocker Assignment.
dc.relation.isversionofjnlnameOperations Research Letters
dc.relation.isversionofjnlvol41
dc.relation.isversionofjnlissue6
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages685-689
dc.relation.isversionofdoi10.1016/j.orl.2013.10.001
dc.relation.isversionofjnlpublisherElsevier
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.updated2016-10-06T09:26:33Z
hal.identifierhal-01499696*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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