Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>

Till Tantau

This paper introduces logspace optimisation problems as

analogues of the well-studied polynomial-time optimisation

problems. Similarly to them, logspace

optimisation problems can have vastly different approximation

properties, even though the underlying existence and budget problems

have the same computational complexity. Numerous natural problems

are presented that exhibit such a varying ...
more >>>