Item

Abstract

Local Ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. At a very high level, a local ratio algorithm first decomposes the input weight function $w$ into a positive linear combination of simpler weight functions or \emph{models}. Guided by this process a solution $S$ is constructed such that $S$ is $\alpha$-approximate with respect to each model used in the decomposition. As a result, $S$ is $\alpha$-approximate under $w$ as well. These models usually have a very simple structure that remains ``unchanged'' throughout the execution of the algorithm. In this work we show that adaptively choosing a model from a richer spectrum of functions can lead to a better local ratio. Indeed, by turning the search for a good model into an optimization problem of its own, we get improved approximations for a data migration problem.