Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
From MaRDI portal
Publication:2867130
DOI10.1007/978-3-319-03780-6_28zbMath1406.68130arXiv1601.01118OpenAlexW2963110996MaRDI QIDQ2867130
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
approximation algorithmoptimization problemlogarithmic spaceapproximation-preserving reduction\(\mathrm{AC}^{0}\)-circuit\(\mathrm{NC}^{1}\)-circuit
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