• 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 - Request a copy

A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts

Aissi, Hassene; Mahjoub, Ali Ridha; McCormick, S. Thomas; Queyranne, Maurice (2014), A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts, Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, Springer : Berlin, p. 25-36. 10.1007/978-3-319-07557-0_3

Type
Communication / Conférence
Date
2014
Conference title
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014
Conference date
2014-06
Conference city
Bonn
Conference country
Germany
Book title
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings
Publisher
Springer
Published in
Berlin
ISBN
978-3-319-07556-3
Number of pages
418
Pages
25-36
Publication identifier
10.1007/978-3-319-07557-0_3
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]
McCormick, S. Thomas
University of British Columbia
Queyranne, Maurice
University of British Columbia
Abstract (EN)
We 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.
Subjects / Keywords
bicriteria global minimum cut problem; parametric complexity

Related items

Showing items related by title and author.

  • Thumbnail
    Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts 
    Aissi, Hassene; McCormick, S. Thomas; Queyranne, Maurice (2020) Communication / Conférence
  • Thumbnail
    Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation 
    Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Article accepté pour publication ou publié
  • Thumbnail
    Separation Algorithms for Single-Machine Scheduling with Precedence Constraints 
    Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Communication / Conférence
  • Thumbnail
    Randomized Contractions for Multiobjective Minimum Cuts 
    Aissi, Hassene; Mahjoub, Ali Ridha; Ravi, Ramamoorthi (2017) Communication / Conférence
  • Thumbnail
    Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut 
    Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) 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