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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ? $\endgroup$– Suresh VenkatJan 30, 2012 at 21:26
-
4$\begingroup$ 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), springerlink.com/content/m52274505l5344g6 $\endgroup$– Jan JohannsenJan 31, 2012 at 8:50
-
3$\begingroup$ Try searching NCAS and FNCAS. $\endgroup$– Tsuyoshi ItoJan 31, 2012 at 14:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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/
