Robust 1-center on trees

Presented at AAAC 2011

p-center problem is to setup p servers for n clients to minimize (max client-server distance)

Edge uncertainty - weights in an interval Vertex uncertainty - weights in an interval

Model differnt weights at different time

Robust = minimize regret over all possible S (particular set of weights)

Improve B&D 2002 algorithm from O(n^3 lg n) to O(n^3) by focusing on 2 bottleneck steps.