2010/11/19 by Pal, Manjish
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.1011.4401
The \sc c-Balanced Separator problem is a graph-partitioning problem in which given a graph G, one aims to find a cut of minimum size such that both the sides of the cut have at least cn vertices. In this paper, we present new directions of progress in the \sc c-Balanced Separator problem. More specifically, we propose a family of mathematical programs, that depend upon a parameter p > 0, and is an extension of the uniform version of the SDPs proposed by Goemans and Linial for this problem. In fact for the case, when p=1, if one can solve this program in polynomial time then simply using the Goemans-Williamson's randomized rounding algorithm for \sc Max Cut \citeWG95 will give an O(1)-factor approximation algorithm for \sc c-Balanced Separator improving the best known approximation factor of O(√(log n)) due to Arora, Rao and Vazirani \citeARV. This family of programs is not convex but one can transform them into so called \emphconcave programs in which one optimizes a concave function over a convex feasible set. It is well known that the optima of such programs lie at one of the extreme points of the feasible set \citeTTT85. Our main contribution is a combinatorial characterization of some extreme points of the feasible set of the mathematical program, for p=1 case, which to the best of our knowledge is the first of its kind. We further demonstrate how this characterization can be used to solve the program in a restricted setting. Non-convex programs have recently been investigated by Bhaskara and Vijayaraghvan \citeBV11 in which they design algorithms for approximating Matrix p-norms although their algorithmic techniques are analytical in nature.