Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-041 | 2nd July 2002 00:00

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint