Abstract

We introduce a new framework for designing and analyzing algorithms. Our framework applies best to problems that are inapproximable according to the standard worst-case analysis. We circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. Given our parameterized approximation, called PArametrized by the Signature of the Solution (PASS) approximation, we design algorithms with optimal approximation ratios for problems with additive and submodular objective functions such as the capacitated maximum facility location problems. We consider two types of algorithms for these problems. For greedy algorithms, our framework provides a justification for preferring a certain natural greedy rule over some alternative greedy rules that have been used in similar contexts. For LP-based algorithms, we show that the natural LP elaxation for these problems is not optimal in our framework. We design a new LP relaxation and show hat this LP relaxation coupled with a new randomized rounding technique is optimal in our framework.
In passing, we note that our results strictly improve over previous results of Kleinberg, Papadimitriou, nd Raghavan [JACM 2004] concerning the approximation ratio of the greedy algorithm.