Logspace Optimization Problems and Their Approximability Properties |
| |
Authors: | Till Tantau |
| |
Affiliation: | (1) Institut fur Theoretische Informatik, Universitat zu Lubeck, 23538 Lubeck, Germany |
| |
Abstract: | Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly
to them, logspace optimization problems can have vastly different approximation properties even though their underlying decision
problems have the same computational complexity. Natural problems - including the shortest path problems for directed graphs,
undirected graphs, tournaments, and forests - exhibit such a varying complexity. In order to study the approximability of
logspace optimization problems in a systematic way, polynomial-time approximation classes and polynomial-time reductions between
optimization problems are transferred to logarithmic space. It is proved that natural problems are complete for different
logspace approximation classes. This is used to show that under the assumption L ≠ NL some logspace optimization 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 optimal solutions cannot be computed in logarithmic
space. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|