All reports by Author Alexander Zelikovsky:

__
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

__
TR97-017
| 5th May 1997
__

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky#### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

__
TR97-004
| 19th February 1997
__

Marek Karpinski, Alexander Zelikovsky#### Approximating Dense Cases of Covering Problems

Comments: 1

__
TR95-030
| 20th June 1995
__

Marek Karpinski, Alexander Zelikovsky#### New Approximation Algorithms for the Steiner Tree Problems

__
TR95-003
| 1st January 1995
__

Marek Karpinski, Alexander Zelikovsky#### 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

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 >>>Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a

given graph $G$ such that the maximum difference between the numbers

of adjacent vertices is minimal. The problem has a long history and

is known to be NP-complete Papadimitriou [Pa76]. Only few special

cases ...
more >>>

Marek Karpinski, Alexander Zelikovsky

We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem asks for the shortest tree connecting

a given set of terminal points in a metric space. We design

new approximation algorithms for the Steiner tree problems

using a novel technique of choosing Steiner points in dependence

on the possible deviation from ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem requires to find a shortest tree connection

a given set of terminal points in a metric space. We suggest a better

and fast heuristic for the Steiner problem in graphs and in

rectilinear plane. This heuristic finds a Steiner tree at ...
more >>>