• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Randomized Contractions for Multiobjective Minimum Cuts

Aissi, Hassene; Mahjoub, Ali Ridha; Ravi, Ramamoorthi (2017), Randomized Contractions for Multiobjective Minimum Cuts, in Pruhs, Kirk; Sohler, Christian, 25th Annual European Symposium on Algorithms (ESA 2017), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 6:1-6:13. 10.4230/LIPIcs.ESA.2017.6

View/Open
mcmc-esa17.pdf (450.8Kb)
Type
Communication / Conférence
Date
2017
Conference title
25th Annual European Symposium on Algorithms (ESA 2017)
Conference date
2017-09
Conference city
Vienna
Conference country
Austria
Book title
25th Annual European Symposium on Algorithms (ESA 2017)
Book author
Pruhs, Kirk; Sohler, Christian
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISBN
978-3-95977-049-1
Pages
6:1-6:13
Publication identifier
10.4230/LIPIcs.ESA.2017.6
Metadata
Show full item record
Author(s)
Aissi, Hassene
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ravi, Ramamoorthi
Computer Science Department - Carnegie Mellon University
Abstract (EN)
We 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.
Subjects / Keywords
minimum cut; multiobjective optimization; budget constraints; graph algorithms; randomized algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts 
    Aissi, Hassene; Mahjoub, Ali Ridha; McCormick, S. Thomas; Queyranne, Maurice (2014) Communication / Conférence
  • Thumbnail
    Étude de formulations étendues pour le problème de l'arbre couvrant budgeté 
    Nourry, Charles; Mahjoub, Ali Ridha; Aissi, Hassene (2022) Communication / Conférence
  • Thumbnail
    Polyhedral Analysis and Branch-and-Cut for the Structural Analysis Problem 
    Lacroix, Mathieu; Mahjoub, Ali Ridha; Martin, Sébastien (2012) Communication / Conférence
  • Thumbnail
    A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints 
    Borne, Sylvie; Mahjoub, Ali Ridha; Taktak, Raouia (2013) Article accepté pour publication ou publié
  • Thumbnail
    Branch-and-Cut-and-Price algorithms for the preemptive RCPSP 
    Fouilhoux, Pierre; Mahjoub, Ali Ridha; Quilliot, Alain; Toussaint, Hélène (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo