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
