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érenceDate
2014Conference title
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014Conference date
2014-06Conference city
BonnConference country
GermanyBook title
Integer Programming and Combinatorial Optimization 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. ProceedingsPublisher
Springer
Published in
Berlin
ISBN
978-3-319-07556-3
Number of pages
418Pages
25-36
Publication identifier
Metadata
Show full item recordAuthor(s)
Aissi, HasseneLaboratoire 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 complexityRelated items
Showing items related by title and author.
-
Aissi, Hassene; McCormick, S. Thomas; Queyranne, Maurice (2020) Communication / Conférence
-
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Communication / Conférence
-
Aissi, Hassene; Mahjoub, Ali Ridha; Ravi, Ramamoorthi (2017) Communication / Conférence
-
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié