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.

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

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

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

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