## Tuesday, January 29, 2008

### 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, \ldots, 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(n^2)\$, whereas the total dual value generated is only \$O(n)\$.

Hence the clean-up step is needed.