Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Approximability and inapproximability for maximum k-edge-colored clustering problem. / Alhamdan, Yousef M.; Kononov, Alexander.
Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. ред. / René van Bevern; Gregory Kucherov. Springer-Verlag GmbH and Co. KG, 2019. стр. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11532 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Approximability and inapproximability for maximum k-edge-colored clustering problem
AU - Alhamdan, Yousef M.
AU - Kononov, Alexander
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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 (formula presented), which significantly improves the best previously known factor (formula presented), obtained by Ageev and Kononov [1]. We also present an upper bound of (formula presented) on the inapproximability of MAX-k-EC. This is the first inapproximability result for this problem.
AB - 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 (formula presented), which significantly improves the best previously known factor (formula presented), obtained by Ageev and Kononov [1]. We also present an upper bound of (formula presented) on the inapproximability of MAX-k-EC. This is the first inapproximability result for this problem.
KW - Clustering
KW - Edge-colored graph
KW - Randomized rounding
KW - APPROXIMATION ALGORITHMS
UR - http://www.scopus.com/inward/record.url?scp=85068611435&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19955-5_1
DO - 10.1007/978-3-030-19955-5_1
M3 - Conference contribution
AN - SCOPUS:85068611435
SN - 9783030199548
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings
A2 - van Bevern, René
A2 - Kucherov, Gregory
PB - Springer-Verlag GmbH and Co. KG
T2 - 14th International Computer Science Symposium in Russia, CSR 2019
Y2 - 1 July 2019 through 5 July 2019
ER -
ID: 20825597