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

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

<p>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.</p>

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

<p>Note PLS might be much easier than FNP.</p>

CC BY-SA 3.0
2014-05-25T08:28:29.300Z
2014-05-25T21:22:28.107Z
2014-05-25T21:22:28.107Z
Rahul Savani
<p>What is the relationship between <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#pls">$\mathsf{PLS}$</a> and <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aA#apx">$\mathsf{APX}$</a>? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a local search algorithm in general?</p>

<cc.complexity-theory><approximation-algorithms>
What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?
argentpepper
# What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

(Asked by: username_0 on 2013-05-23)

What is the relationship between [$\mathsf{PLS}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#pls) and [$\mathsf{APX}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aA#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?

**Tags:** cc.complexity-theory, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2014-05-25. Score: 6

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.


---

