AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The Local Ratio Technique is a well-known paradigms for designing approximation algorithms for combinatorial optimization problems. At the heart of every Local Ratio algorithm is the update step in which the weight function is modified by subtracting a certain "model" function w_i. Guided by this process, a solution S is constructed such that w_i(S) <= r * w_i(A) for all A and i. Thus, S is r-approximate since the input weight function can be written as w_1 + ... + w_k.

Typically, these model functions have a very simple structure that remains "unchanged" throughout the execution of the algorithm. In this talk we will see 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 the Data Migration problem.

Julian Mestre

--email hidden

passcode not visible

logged in users only