|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Approximability and inapproximability for maximum k-edge-colored clustering problemтезисы доклада
- Авторы: Alhamdan Y.M., Kononov A.
- Сборник: Computer Science – Theory and Applications. CSR 2019
- Серия: Lecture Notes in Computer Science
- Том: 11532
- Тезисы
- Год издания: 2019
- Место издания: Springer, Cham Cham
- Первая страница: 1
- Последняя страница: 12
- DOI: 10.1007/978-3-030-19955-5_1
- Аннотация: We consider the Max k-Edge-Colored Clustering problem (abbreviated as MAX-k-EC). We are given an edge-colored graph with k colors. Each edge of the graph has a positive weight. We seek to color the vertices of the graph so as to maximize the total weight of the edges which have the same color at their extremities. The problem was introduced by Angel et al. [2]. We give a polynomial-time algorithm for MAX-k-EC with an approximation factor 0.34 which significantly improves the best previously known factor 0.304 obtained by Ageev and Kononov [1]. We also present an upper bound of 0.972 on the inapproximability of MAX-k-EC. This is the first inapproximability result for this problem.
- Добавил в систему: Кононов Александр Вениаминович