Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIMATION ALGORITHM:
Reports tagged with Approximation algorithm:
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 >>>

TR02-054 | 5th September 2002
Detlef Sieling

#### Minimization of Decision Trees is Hard to Approximate

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

#### Deterministic clustering with data nets

We consider the $K$-clustering problem with the $\ell_2^2$
distortion measure, also known as the problem of optimal
fixed-rate vector quantizer design. We provide a deterministic
approximation algorithm which works for all dimensions $d$ and
which, given a data set of size $n$, computes in time
more >>>

TR04-084 | 28th September 2004
George Karakostas

#### A better approximation ratio for the Vertex Cover problem

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$
(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,
and by Monien and Speckenmeyer in 1985. The improvement of the vanishing
factor comes as an application of the recent results of Arora, Rao, and Vazirani
that improved ... more >>>

TR06-007 | 23rd November 2005
#### Approximating Buy-at-Bulk $k$-Steiner trees
In the buy-at-bulk $k$-Steiner tree (or rent-or-buy
$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set
of terminals $T\subseteq V$ including a particular vertex $s$ called
the root, and an integer $k\leq |T|$. There are two cost functions