Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems

DOI10.1007/978-3-319-03780-6_28zbMath1406.68130arXiv1601.01118OpenAlexW2963110996MaRDI QIDQ2867130

Tomoyuki Yamakami

Publication date: 10 December 2013

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.01118

zbMATH Keywords

approximation algorithmoptimization problemlogarithmic spaceapproximation-preserving reduction\(\mathrm{AC}^{0}\)-circuit\(\mathrm{NC}^{1}\)-circuit

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Approximation in (Poly-) logarithmic space ⋮ Unnamed Item ⋮ Approximation in (Poly-) Logarithmic Space

Cites Work

• Unnamed Item
• Unnamed Item
• The maximum flow problem is log space complete for P
• A very hard log-space counting class
• Logspace optimization problems and their approximability properties
• Undirected connectivity in log-space