  We present a new local-search algorithm for the $k$-median clustering
problem. We show that local optima for this algorithm give a
$(2.836+\epsilon)$-approximation; our result improves upon the
$(3+\epsilon)$-approximate local-search algorithm of Arya et al. [STOC 01].
Moreover, a computer-aided analysis of a natural extension suggests that this
approach may lead to an improvement over the best-known approximation guarantee
for the problem. The new ingredient in our algorithm is the use of a potential
function based on both the closest and second-closest facilities to each
client. Specifically, the potential is the sum over all clients, of the
distance of the client to its closest facility, plus (a small constant times)
the truncated distance to its second-closest facility. We move from one
solution to another only if the latter can be obtained by swapping a constant
number of facilities, and has a smaller potential than the former. This refined
potential allows us to avoid the bad local optima given by Arya et al. for the
local-search algorithm based only on the cost of the solution.
