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

Jacobo Toran, Florian Wörz

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>