Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Covering Problems:
TR07-027 | 2nd February 2007
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

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

TR22-137 | 26th September 2022
Daniel Avraham , Amir Yehudayoff

On blocky ranks of matrices

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>

ISSN 1433-8092 | Imprint