Institut für Informatik
 
Abteilung V

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

28.10.2002

Polynomial Time Approximation Schemes for Metric MIN-BISECTION (Extended Version)
W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon
[Download PostScript] [Download PDF]

We design the first polynomial time approximation schemes (PTASs) 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.Our approximation schemes depend on a novel hybrid metric placement method and a new application of linearized quadratic programs.

Last Change: 11/05/14 at 10:24:25
 English
Universität Bonn -> Institut für Informatik -> Abteilung V