非表示:
キーワード:
-
要旨:
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.
