Wissen, was gut ist. Studieren in Chemnitz.
Armbruster, Michael; Fügenschuh, Marzena; Helmberg, Christoph; Martin, Alexander : On the Graph Bisection Cut polytope

Armbruster, Michael ; Fügenschuh, Marzena ; Helmberg, Christoph ; Martin, Alexander : On the Graph Bisection Cut polytope

Author(s):
Armbruster, Michael
Fügenschuh, Marzena
Helmberg, Christoph
Martin, Alexander
Title:
On the Graph Bisection Cut polytope
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 20, 2006
Mathematics Subject Classification:
90C57 [ Polyhedral combinatorics, branch-and-bound, branch-and-cut ]
Abstract:
Given a graph $G=(V,E)$ with node weights $f_v \in \mathbb{N}_0,\, v\in V$, and some number $F\in \mathbb{N}_0$, the convex hull of the incidence vectors of all cuts $\delta(S),\, S\subseteq V$ with $f(S)\le F$ and $f(V\setminus S)\le F$ is called the {\em bisection cut polytope}. We study the facial structure of this polytope which shows up in many graph partitioning problems with applications in VLSI-design or frequency assignment. We give necessary and in some cases sufficient conditions for the knapsack tree inequalities to be facet-defining. We extend these inequalities to a richer class by exploiting that each cut intersects each cycle in an even number of edges. Finally, we present a new class of inequalities that are based on non-connected substructures yielding non-linear right-hand sides. We show that the supporting hyperplanes of the convex envelope of this non-linear function correspond to the faces of the so-called {\em cluster weight polytope}, for which we give a complete description under certain conditions.
Keywords:
polyhedral combinatorics, minimum bisection problem, knapsack tree inequality, bisection knapsack walk inequality, cluster weight polytope
Language:
English
Publication time:
11 / 2006