Peter Gritzmann, TU M"unchen, gritzman@ma.tum.de
Abstract:
The talk deals with quite general geoemtric clustering problems that are however motivated by their application to a new lend-lease initiative for the consolidation of farmland. Of course, the underlying optimization problem is NP-hard even in the most simple cases.
We give and analyze a new approximate 0-1-convex optimization algorithm, where in effect the centers of gravity of the clusters are pushed apart. The core of the method is based on the use of appropriate Minkowski spaces. A particularly important example is that of the spaces whose unit balls stems from the dual of the cartesian product of permutahedra. It is shown that these unit balls themselves can be tightly approximated by Hardamard matrix based polytopes with only linearly many facets. The facet normals are then used as objective function vectors for a polynomial-time linear programming approximation algorithm. We derive theoretical results including some on "Voronoi-separation", givee a worst case bound for the approximation error but also report on the practical performance of this method for land consolidation in Northern Bavaria, Germany.
(Joint work with Andreas Brieden, Munich)