Random rewards, fractional Brownian local times and stable self-similar processes

Abstract

We give deterministic versions of randomized approximation algorithms for several ranking and clustering problems that were proposed by Ailon, Charikar and Newman. We show that under a reasonable extension of the triangle inequality in clustering problems, we can resolve Ailon et al.'s open question wehter there is an approximation algorithm for weighted correlation clustering with weights satisfying the triangle inequality.