Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-077 | 4th September 2003 00:00

Logspace Optimisation Problems and their Approximation Properties



This paper introduces logspace optimisation problems as
analogues of the well-studied polynomial-time optimisation
problems. Similarly to them, logspace
optimisation problems can have vastly different approximation
properties, even though the underlying existence and budget problems
have the same computational complexity. Numerous natural problems
are presented that exhibit such a varying complexity. They include
the shortest path problems for directed graphs, undirected graphs,
tournaments, and forests. In order to study the approximability
of logspace optimisation problems in a systematic way,
polynomial-time approximation classes are transferred to logarithmic
space. Appropriate reductions are defined and optimisation problems
are presented that are complete for these classes. It is shown that
under the assumption L \neq NL some natural logspace
optimisation problems cannot be approximated with a constant ratio;
some can be approximated with a constant ratio, but do not permit a
logspace approximation scheme; and some have a logspace
approximation scheme, but cannot be solved in logarithmic space. An
example of a problem of the latter type is the shortest
path problem for tournaments.

ISSN 1433-8092 | Imprint