What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a local search algorithm in general?


1 Answer 1


If one wants to approximate the potential function, then yes, there even exists a fully polynomial-time approximation scheme (FPTAS). See

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Approximate Local Search in Combinatorial Optimization. SIAM J. Comput. 33(5): 1201-1214 (2004).

For some settings though, this is not interesting. For example, for congestion games, where pure equilibria exist and their computation is PLS-complete, strategy profiles that approximate the potential function well may be very poor approximate equilibria. For some settings, constant-factor approximate equilibria can be computed in polynomial-time even when computing an exact equilibrium is PLS-hard, for other settings it is PLS-hard to compute an approximate equilibrium for any polynomial-time computable non-trivial approximation factor, as explained by the following announcement paper.

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik: Computing approximate pure Nash equilibria in congestion games. SIGecom Exchanges 11(1): 26-29 (2012).

Note PLS might be much easier than FNP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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