Approximation Schemes for Metric Minimum Bisection and Partitioning

We design polynomial time approximation schemes (PTASs) for Metric MINBISECTION, i.e. dividing a given nite metric space into two halves so as to minimize the sum of distances across the cut. The method extends to partitioning problems with arbitrary size constraints. Our approximation schemes depend on a hybrid placement method and on a new application of linearized quadratic programs