Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem | Sciact - Система учета научной деятельности ИМ СО РАН

Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem Научная публикация

Конференция

14th International Computer Science Symposium in Russia
01-05 июл. 2019 , Novosibirsk, Russia,

Журнал

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Вых. Данные

Год: 2019, Том: 11532, Страницы: 1-12 Страниц : 12 DOI: 10.1007/978-3-030-19955-5_1

Авторы

Alhamdan Yousef M. ¹ , Kononov Alexander ^1,2

Организации

1	Mathematics and Mechanics Department, Novosibirsk State University, Novosibirsk, Russia
2	Laboratory “Mathematical Models of Decision Making”, Sobolev Institute of Mathematics, Novosibirsk, Russia

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 49/144≈0.34, which significantly improves the best previously known factor 7/23≈0.304, obtained by Ageev and Kononov [1]. We also present an upper bound of 241/248≈0.972 on the inapproximability of MAX-k-EC. This is the first inapproximability result for this problem.

Alhamdan Y.M. , Kononov A.
Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem
Lecture Notes in Computer Science. 2019. V.11532. P.1-12. DOI: 10.1007/978-3-030-19955-5_1 Scopus OpenAlex

Опубликована online:

16 мая 2019 г.

Scopus:	2-s2.0-85068611435
OpenAlex:	W2952132033

БД	Цитирований
OpenAlex	4
Scopus	7