|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-Reports 2003 | Copyright 2003 Universität Bonn, Institut für Informatik, Abt. V | |
|
85250 05.05.2003 |
Approximation Schemes for Metric Minimum Bisection and Partitioning
W. Fernandez de la Vega, Marek Karpinski and Claire Kenyon [Download PostScript] [Download PDF] We design polynomial time approximation schemes (PTASs) for Metric MIN-BISECTION, i.e. dividing a given {finite 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. |
|
|
Last Change:
11/05/14 at 10:28:05
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |