
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 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
