Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with approximation scheme:
TR01-084 | 1st October 2001
Gerhard J. Woeginger

When does a dynamic programming formulation guarantee the existence of an FPTAS?

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).

... more >>>

TR02-025 | 26th April 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

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 >>>

TR03-077 | 4th September 2003
Till Tantau

Logspace Optimisation Problems and their Approximation Properties

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 >>>

ISSN 1433-8092 | Imprint