Example for Primal-Dual fixed

The bad example for the primal-dual algorithm that I cooked up in class did not give the large gap I was hoping for, though going in the right direction. Instead, consider the following example:

There are $2n$ clients and $n$ potential facilities. The first $n$ of the clients (say $v_1,v_2,\dots ,v_n$) are at distance 1 to all the facilities, we call these communal clients.

For the other $n$ clients: client $v_{n+i}$ is at distance $1$ to facility $u_i$ and at distance 3 to all other facilities. (We say client $v_{n+i}$ is facility $u_i$'s private client.)

The first facility $u_1$ costs $n+1$, and all the others cost $n+2$.

If we raise duals uniformly, then at time $t=2$, the first facility $u_1$ will become tentatively opened, and all the communal clients, and private client $u_{n+1}$ become frozen. But the other private clients will continue to raise their duals, and at time $t=3$, all the remaining facilities will also become tentatively open.

Note that the cost of actually opening all these tentatively open facilities would be $(n+1)+(n-1)(n+2)=\Omega \left(n^2\right)$, whereas the total dual value generated is only $O\left(n\right)$.

Hence the clean-up step is needed.