Most computational tasks that arise in realistic scenarios are intractable,
at least if one insists on exact solutions delivered with certainty within
a strict deadline. Nevertheless, necessity dictates that acceptable solutions
of some kind must be found.
Two means for circumventing the intractability barrier are: randomized
computation, where the answer is required to be optimal with high probability
but not with certainty, and approximate computation, where the answer is
guaranteed to be within, say, small percentage of optimality.
RAND-APX ("Randomized and Approximate Computation") is a Thematic
Network funded under the European IST Programme, with
in Bonn, Edinburgh,
and the Weizmann Institute, Rehovot.
Its aim is to promote research in
foundational aspects of randomized and approximate computation.