ECCC-Report TR03-077https://eccc.weizmann.ac.il/report/2003/077Comments and Revisions published for TR03-077en-usMon, 20 Oct 2003 12:18:07 +0200
Paper TR03-077
| Logspace Optimisation Problems and their Approximation Properties |
Till Tantau
https://eccc.weizmann.ac.il/report/2003/077This 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.
Mon, 20 Oct 2003 12:18:07 +0200https://eccc.weizmann.ac.il/report/2003/077