Show simple item record

dc.contributor.authorAissi, Hassene*
dc.contributor.authorMahjoub, Ali Ridha*
dc.contributor.authorMcCormick, S. Thomas*
dc.contributor.authorQueyranne, Maurice*
dc.date.accessioned2016-02-09T09:59:05Z
dc.date.available2016-02-09T09:59:05Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15355
dc.language.isoenen
dc.subjectbicriteria global minimum cut problemen
dc.subjectparametric complexityen
dc.subject.ddc003en
dc.titleA Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cutsen
dc.typeCommunication / Conférence
dc.description.abstractenWe investigate the bicriteria global minimum cut problem where each edge is evaluated by two nonnegative cost functions. The parametric complexity of such a problem is the number of linear segments in the parametric curve when we take all convex combinations of the criteria. We prove that the parametric complexity of the global minimum cut problem is O(|V|3). As a consequence, we show that the number of non-dominated points is O(|V|7) and give the first strongly polynomial time algorithm to compute these points. These results improve on significantly the super-polynomial bound on the parametric complexity given by Mulmuley [11], and the pseudo-polynomial time algorithm of Armon and Zwick [1] to solve this bicriteria problem. We extend some of these results to arbitrary cost functions and more than two criteria, and to global minimum cuts in hypergraphs.en
dc.identifier.citationpages25-36en
dc.relation.ispartoftitleInteger Programming and Combinatorial Optimization 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedingsen
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2014
dc.relation.ispartofpages418en
dc.relation.ispartofurl10.1007/978-3-319-07557-0en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-07556-3en
dc.relation.conftitleInteger Programming and Combinatorial Optimization 17th International Conference, IPCO 2014en
dc.relation.confdate2014-06
dc.relation.confcityBonnen
dc.relation.confcountryGermanyen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-07557-0_3en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2016-02-09T09:32:15Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds251768*
hal.person.labIds251768*
hal.identifierhal-01277103*


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