|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Improved Approximation for the Max k-Colored Clustering Problemтезисы доклада
- Авторы: Ageev A., Kononov A.
- Сборник: Approximation and Online Algorithms. WAOA 2014
- Серия: Springer Lecture Notes in Computer Science
- Том: 7936
- Тезисы
- Год издания: 2015
- Место издания: Springer, Cham Cham
- Первая страница: 134
- Последняя страница: 146
- DOI: 10.1007/978-3-319-18263-6_1
- Аннотация: In the Max k-Colored Clustering Problem we are given an undirected graph . Each edge of has a nonnegative weight and a color . It is required to assign a color from to each vertex of so as to maximize the total weight of edges whose both endpoints have the same color as the color of the edge. Angel et al. [1] show that the problem is strongly NP-hard and present a randomized constant-factor approximation algorithm for solving it. We improve this result in two directions. First, we give a more careful analysis of the algorithm in [1], which significantly improves on its approximation bound (0.25 instead of 0.135). Second, we present a different algorithm with a better worst case performance guarantee of 0.304. Both algorithms are based on using similar randomized rounding schemes for a natural LP relaxation of the problem. They can be derandomized in a standard way by computing conditional expectations for some estimate function.
- Добавил в систему: Кононов Александр Вениаминович