• 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

Separating Partition Inequalities

Baïou, Mourad; Barahona, Francisco; Mahjoub, Ali Ridha (2000), Separating Partition Inequalities, Mathematics of Operations Research, 25, 2, p. 243-254. http://dx.doi.org/10.1287/moor.25.2.243.12223

Type
Article accepté pour publication ou publié
Date
2000
Journal name
Mathematics of Operations Research
Volume
25
Number
2
Publisher
Informs
Pages
243-254
Publication identifier
http://dx.doi.org/10.1287/moor.25.2.243.12223
Metadata
Show full item record
Author(s)
Baïou, Mourad
Barahona, Francisco
Mahjoub, Ali Ridha
Abstract (EN)
Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x({delta}(S1,...,Sp))≥ap+b. Here {delta}(S1,...,Sp) denotes the multicut defined by a partition S1,...,Sp of V. Partition inequalities arise as valid inequalities for optimization problems related to k-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x({delta}(S1,...,Sp))–p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities.
Subjects / Keywords
k-connected subgraphs; submodular functions; separation problem; Partition inequalities

Related items

Showing items related by title and author.

  • Thumbnail
    Partition Inequalities: Separation, Extensions and Network Design, 
    Mahjoub, Ali Ridha; Barahona, Francisco; Baïou, Mourad (2011) Chapitre d'ouvrage
  • Thumbnail
    Steiner 2-edge connected subgraph polytopes on series-parallel graphs 
    Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
  • Thumbnail
    The Steiner Traveling Salesman Polytope and Related Polyhedra 
    Baïou, Mourad; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
  • Thumbnail
    Composition of graphs and polyhedra I : Balanced induced subgraphs and acyclic subgraphs 
    Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
  • Thumbnail
    Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs 
    Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994) 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