P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou
studied in [Gopalan et al., ICALP2006] connectivity properties of the
solution-space of Boolean formulas, and investigated complexity issues
on connectivity problems in Schaefer's framework [Schaefer, STOC1978].
A set S of logical relations is Schaefer if all relations in ... more >>>

Implicit algorithms work on their input's characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms ... more >>>

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