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 reductionspolynomial-time approximation

Mathematics Subject Classification ID

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

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

(14)

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

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)