  We present a deterministic polynomial-time algorithm for computing
$d^{d+o(d)}$-approximate (pure) Nash equilibria in (proportional sharing)
weighted congestion games with polynomial cost functions of degree at most $d$.
This is an exponential improvement of the approximation factor with respect to
the previously best deterministic algorithm. An appealing additional feature of
the algorithm is that it only uses best-improvement steps in the actual game,
as opposed to the previously best algorithms, that first had to transform the
game itself. Our algorithm is an adaptation of the seminal algorithm by
Caragiannis et al. [FOCS'11, TEAC 2015], but we utilize an approximate
potential function directly on the original game instead of an exact one on a
modified game.
  A critical component of our analysis, which is of independent interest, is
the derivation of a novel bound of $[d/\mathcal{W}(d/\rho)]^{d+1}$ for the
Price of Anarchy (PoA) of $\rho$-approximate equilibria in weighted congestion
games, where $\mathcal{W}$ is the Lambert-W function. More specifically, we
show that this PoA is exactly equal to $\Phi_{d,\rho}^{d+1}$, where
$\Phi_{d,\rho}$ is the unique positive solution of the equation $\rho
(x+1)^d=x^{d+1}$. Our upper bound is derived via a smoothness-like argument,
and thus holds even for mixed Nash and correlated equilibria, while our lower
bound is simple enough to apply even to singleton congestion games.
