<p>This one seems related, although it focuses more on parallel time (NC) rather than the closely related space (L): <a href="http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/">http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/</a></p>

CC BY-SA 3.0
2012-01-31T20:07:52.780Z
2012-01-31T20:07:52.780Z
Noam
<p>What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\mathsf{NC}$ approximation schemes", analogous to $\mathsf{FPTAS}$ for $\mathsf{NP}$ optimization problems?</p>

CC BY-SA 3.0
2012-01-30T21:26:28.940Z
Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ?
Suresh Venkat
CC BY-SA 3.0
2012-01-31T08:50:12.347Z
You might be interested in this paper:
Till Tantau, Logspace Optimization Problems and Their Approximability Properties, Theory of Computing Systems 41(2), pp. 327-350 (2007), http://www.springerlink.com/content/m52274505l5344g6/
Jan Johannsen
CC BY-SA 3.0
2012-01-31T14:31:58.377Z
Try searching NCAS and FNCAS.
Tsuyoshi Ito
<reference-request><approximation-algorithms><optimization>
Approximation schemes for P-complete problems?
argentpepper
# Approximation schemes for P-complete problems?

(Asked by: username_0 on 2012-01-30)

What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\mathsf{NC}$ approximation schemes", analogous to $\mathsf{FPTAS}$ for $\mathsf{NP}$ optimization problems?

**Tags:** reference-request, approximation-algorithms, optimization

> **Comments:**
> **username_1**: Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ?  
> **username_2**: You might be interested in this paper: Till Tantau, Logspace Optimization Problems and Their Approximability Properties, Theory of Computing Systems 41(2), pp. 327-350 (2007), http://www.springerlink.com/content/m52274505l5344g6/  
> **username_3**: Try searching NCAS and FNCAS.  

---

## 1 answers

### Answer by username_4 on 2012-01-31. Score: 5

This one seems related, although it focuses more on parallel time (NC) rather than the closely related space (L): <http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/>


---

