Show simple item record

Randomized Contractions for Multiobjective Minimum Cuts

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorAissi, Hassene
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha
hal.structure.identifierComputer Science Department - Carnegie Mellon University
dc.contributor.authorRavi, Ramamoorthi
dc.date.accessioned2019-12-13T11:01:04Z
dc.date.available2019-12-13T11:01:04Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20317
dc.language.isoenen
dc.subjectminimum cuten
dc.subjectmultiobjective optimizationen
dc.subjectbudget constraintsen
dc.subjectgraph algorithmsen
dc.subjectrandomized algorithmsen
dc.subject.ddc005en
dc.titleRandomized Contractions for Multiobjective Minimum Cutsen
dc.typeCommunication / Conférence
dc.description.abstractenWe show that Karger's randomized contraction method (SODA 93) can be adapted to multiobjective global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms. For global minimum cuts with a single edge-budget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an n-node graph improving upon the best-known randomized algorithm with running time tilde{O}(n^4) due to Armon and Zwick (Algorithmica 2006). Our analysis also gives a new upper bound of O(n^3) for the number of optimal solutions for a single edge-budget min cut problem. For the case of (k-1) edge-budget constraints, the extension of our algorithm saves a logarithmic factor from the best-known randomized running time of O(n^{2k} log^3 n). A main feature of our algorithms is to adaptively choose, at each step, the appropriate cost function used in the random selection of edges to be contracted. For the global min cut problem with a constant number of node budgets, we give a randomized algorithm with running time tilde{O}(n^2), improving the current best determinisitic running time of O(n^3) due to Goemans and Soto (SIAM Journal on Discrete Mathematics 2013). Our method also shows that the total number of distinct optimal solutions is bounded by O(n^2) as in the case of global min-cuts. Our algorithm extends to the node-budget constrained global min cut problem excluding a given sink with the same running time and bound on number of optimal solutions, again improving upon the best-known running time by a factor of O(n). For node-budget constrained problems, our improvements arise from incorporating the idea of merging any infeasible super-nodes that arise during the random contraction process. In contrast to cuts excluding a sink, we note that the node-cardinality constrained min-cut problem containing a given source is strongly NP-hard using a reduction from graph bisection.en
dc.identifier.citationpages6:1-6:13en
dc.relation.ispartoftitle25th Annual European Symposium on Algorithms (ESA 2017)en
dc.relation.ispartofeditorPruhs, Kirk
dc.relation.ispartofeditorSohler, Christian
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofdate2017
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-95977-049-1en
dc.relation.conftitle25th Annual European Symposium on Algorithms (ESA 2017)en
dc.relation.confdate2017-09
dc.relation.confcityViennaen
dc.relation.confcountryAustriaen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.ESA.2017.6en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-12-13T10:52:26Z
hal.identifierhal-02409110*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
mcmc-esa17.pdf
Size:
450.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record