Random rewards, fractional Brownian local times and stable self-similar processes
Collections
Author
Cohen, S.
Samorodnitsky, G.
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.
Date Issued
2005-08
Publisher
Cornell University Operations Research and Industrial Engineering
Keywords
Previously Published as
1430
Type
technical report