|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2002 | Copyright 2002 University of Bonn, Department of Computer Science, Abt. V | |
|
8980 July 16, 2002 |
A Polynomial Time Approximation Scheme for Metric MIN-BISECTION
W. Fernandez de la Vega, Marek Karpinski and Claire Kenyon [Download PostScript] [Download PDF] We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across that partition. The method of solution depends on a new metric placement partitioning method which could be also of independent interest. |
|
|
Last Change:
11/05/14 at 10:24:52
|
University of Bonn -> Department of Computer Science -> Chair V | |