Show simple item record

Separating Partition Inequalities

dc.contributor.authorBaïou, Mourad
HAL ID: 173977
dc.contributor.authorBarahona, Francisco
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-06T07:52:11Z
dc.date.available2010-04-06T07:52:11Z
dc.date.issued2000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3824
dc.language.isoenen
dc.subjectk-connected subgraphsen
dc.subjectsubmodular functionsen
dc.subjectseparation problemen
dc.subjectPartition inequalitiesen
dc.subject.ddc003en
dc.titleSeparating Partition Inequalitiesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven 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.isversionofjnlnameMathematics of Operations Research
dc.relation.isversionofjnlvol25en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2000-05
dc.relation.isversionofjnlpages243-254en
dc.relation.isversionofdoihttp://dx.doi.org/10.1287/moor.25.2.243.12223en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherInformsen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record