Petr Slavik

We establish significantly improved bounds on the performance of the greedy

algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our

improvements result from a new approach to both problems. In particular,

(a) we improve the known bound on the performance ratio of the greedy ...
more >>>

Sanjeev Khanna, Madhu Sudan, David P. Williamson

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier ...
more >>>

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

This paper continues the work initiated by Creignou [Cre95] and

Khanna, Sudan and Williamson [KSW96] who classify maximization

problems derived from boolean constraint satisfaction. Here we

study the approximability of {\em minimization} problems derived

thence. A problem in this framework is characterized by a

collection F ...
more >>>

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

Given a finite set $S$ of points (i.e. the stations of a radio

network) on a $d$-dimensional Euclidean space and a positive integer

$1\le h \le |S|-1$, the \minrangeh{d} problem

consists of assigning transmission ranges to the stations so as

to minimize the total power consumption, provided ...
more >>>

Bodo Manthey

A cycle cover of a graph is a set of cycles such that every vertex is

part of exactly one cycle. An L-cycle cover is a cycle cover in which

the length of every cycle is in the set L. The weight of a cycle cover

of an edge-weighted graph ...
more >>>

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.

We consider the approximation ability of randomized search for the class of ...
more >>>