|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problemтезисы доклада
- Авторы: Ageev A., Kononov A.
- Сборник: Mathematical Optimization Theory and Operations Research. MOTOR 2020
- Серия: Communications in Computer and Information Science
- Том: 1275
- Тезисы
- Год издания: 2020
- Место издания: Springer, Cham Cham
- Первая страница: 3
- Последняя страница: 15
- DOI: 10.1007/978-3-030-58657-7_1
- Аннотация: In the Max k-Edge-Colored Clustering problem (abbreviated as MAX-k-EC) we are given an undirected graph and k colors. Each edge of the graph has a color and a nonnegative weight. The goal is to color the vertices so as to maximize the total weight of the edges whose colors coincide with the colors of their endpoints. The problem was introduced by Angel et al. [3]. In this paper we give a polynomial-time algorithm for MAX-k-EC with an approximation factor 0.3622 which significantly improves the best previously known approximation bound 0.3402 established by Alhamdan and Kononov [2].
- Добавил в систему: Кононов Александр Вениаминович