Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
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.
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008
Reena Elangovan, Shubham Jain, et al.
ACM TODAES
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998