TR02-041 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

Publication: 2nd July 2002 18:08

Downloads: 1887

Keywords:

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.