__
TR03-077 | 4th September 2003 00:00
__

#### Logspace Optimisation Problems and their Approximation Properties

TR03-077
Authors:

Till Tantau
Publication: 20th October 2003 12:18

Downloads: 2165

Keywords:

Approximation,

approximation scheme,

independence number,

Logspace,

optimization,

planar-embedded graphs,

reachability,

shortest path,

Symmetric Logspace,

Tournaments,

undirected graphs
**Abstract:**
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.