Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x(δ(S1,...,Sp))≥ap+b. Here δ(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(δ(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.
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics