Klaus Weihrauch

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

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

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

Marek Karpinski

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.

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

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

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