Nonpolyhedral Relaxations of Graph-Bisection Problems

• DOI: 10.1137/0805024
• Publication Date: 2005-02-23T10:50:53Z
• Authors: Svatopluk Poljak; Franz Rendl
• Keywords: Cardinality (data modeling); Maximum cut; Bisection; Duality (order theory)

We study the problem of finding minimum bisection a graph into two parts prescribed sizes. formulate lower bounds on by relaxing node- and edge- incidence vectors cuts. prove that both relaxations provide same bound. The main fact we is duality between relaxed preserves very natural cardinality constraints present an analogous result also for max-cut problem, show relation edge relaxation some other optimality criteria studied before. Finally, briefly mention possible applications practical computational approach.