期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
