Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2002 Copyright 2002 Universität Bonn, Institut für Informatik, Abt. V
85240

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V