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?

  • 2
    $\begingroup$ Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ? $\endgroup$ Jan 30 '12 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 31 '12 at 8:50
  • 3
    $\begingroup$ Try searching NCAS and FNCAS. $\endgroup$ Jan 31 '12 at 14:31

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/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.