Logspace optimization problems and their approximability properties

DOI10.1007/S00224-007-2011-1MaRDI QIDQ2642909zbMATH OpenOpenAlexFDO

Authors Till Tantau

Publication date 6 September 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-007-2011-1

zbMATH Keywords

logarithmic spacepolynomial-time approximationpolynomial-time reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Fundamentals of Computation Theory
• Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
• scientific article; zbMATH DE number 847149
• Optimization, approximation, and complexity classes
• Approximating linear programming is log-space complete for P

Cited in

(15)

• A note on logspace optimization
• Approximation in (poly-) logarithmic space
• Depth-first search in directed planar graphs, revisited
• Frameworks for designing in-place graph algorithms
• Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
• A Logspace Algorithm for Partial 2-Tree Canonization
• scientific article; zbMATH DE number 5763313 (Why is no real title available?)
• Log-space algorithms for paths and matchings in k-trees
• A framework for in-place graph algorithms
• Approximation in (Poly-) Logarithmic Space
• scientific article; zbMATH DE number 7204396 (Why is no real title available?)
• Fundamentals of Computation Theory
• On stalling in LogP
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• Logical expressibility of syntactic NL for complementarity and maximization

This page was built for publication: Logspace optimization problems and their approximability properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642909)