ECCC-Report TR02-041https://eccc.weizmann.ac.il/report/2002/041Comments and Revisions published for TR02-041en-usTue, 02 Jul 2002 18:08:32 +0300
Paper TR02-041
| A Polynomial Time Approximation Scheme for Metric MIN-BISECTION |
Wenceslas Fernandez de la Vega,
Marek Karpinski,
Claire Kenyon
https://eccc.weizmann.ac.il/report/2002/041We 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.
Tue, 02 Jul 2002 18:08:32 +0300https://eccc.weizmann.ac.il/report/2002/041