Random rewards, fractional Brownian local times and stable self-similar processes
Cohen, S.; Samorodnitsky, G.
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.
Cornell University Operations Research and Industrial Engineering
Operations Research; Industrial Engineering; technical report
Previously Published As