• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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
Titre du colloque
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014
Date du colloque
2014-06
Ville du colloque
Bonn
Pays du colloque
Germany
Titre de l'ouvrage
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings
Éditeur
Springer
Ville d’édition
Berlin
Isbn
978-3-319-07556-3
Nombre de pages
418
Pages
25-36
Identifiant publication
10.1007/978-3-319-07557-0_3
Métadonnées
Afficher la notice complète
Auteur(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
Résumé (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.
Mots-clés
bicriteria global minimum cut problem; parametric complexity

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Randomized Contractions for Multiobjective Minimum Cuts 
    Aissi, Hassene; Mahjoub, Ali Ridha; Ravi, Ramamoorthi (2017) Communication / Conférence
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval 
    Kacem, Imed; Mahjoub, Ali Ridha (2009) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo