| dc.contributor.author | Baïou, Mourad | |
| dc.contributor.author | Barahona, Francisco | |
| dc.contributor.author | Mahjoub, Ali Ridha | |
| dc.date.accessioned | 2010-04-06T07:52:11Z | |
| dc.date.available | 2010-04-06T07:52:11Z | |
| dc.date.issued | 2000 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/3824 | |
| dc.language.iso | en | en |
| dc.subject | k-connected subgraphs | en |
| dc.subject | submodular functions | en |
| dc.subject | separation problem | en |
| dc.subject | Partition inequalities | en |
| dc.subject.ddc | 003 | en |
| dc.title | Separating Partition Inequalities | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | 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. | en |
| dc.relation.isversionofjnlname | Mathematics of Operations Research | |
| dc.relation.isversionofjnlvol | 25 | en |
| dc.relation.isversionofjnlissue | 2 | en |
| dc.relation.isversionofjnldate | 2000-05 | |
| dc.relation.isversionofjnlpages | 243-254 | en |
| dc.relation.isversionofdoi | http://dx.doi.org/10.1287/moor.25.2.243.12223 | en |
| dc.description.sponsorshipprivate | oui | en |
| dc.relation.isversionofjnlpublisher | Informs | en |
| dc.subject.ddclabel | Recherche opérationnelle | en |
