Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Metric Spaces:
TR02-014 | 10th December 2001
Klaus Weihrauch

Computational Complexity on Computable Metric Spaces

Revisions: 1

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

TR02-041 | 2nd July 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

We design a polynomial time approximation scheme (PTAS) 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. The method of solution depends on a new metric placement
partitioning ... more >>>

TR02-046 | 16th July 2002
Marek Karpinski

On Approximability of Minimum Bisection Problem

We survey some recent results on the complexity of computing
approximate solutions for instances of the Minimum Bisection problem
and formulate some intriguing and still open questions about the
approximability status of that problem. Some connections to other
optimization problems are also indicated.

more >>>

TR08-094 | 10th October 2008
Piotr Berman, Marek Karpinski, Alexander Zelikovsky

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

more >>>

TR15-072 | 23rd April 2015
Roei Tell

On Being Far from Far and on Dual Problems in Property Testing

Revisions: 4

For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing ... more >>>

ISSN 1433-8092 | Imprint