Standard

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. ed. / René van Bevern; Gregory Kucherov. Springer-Verlag GmbH and Co. KG, 2019. p. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11532 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Alhamdan, YM & Kononov, A 2019, Approximability and inapproximability for maximum k-edge-colored clustering problem. in R van Bevern & G Kucherov (eds), Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11532 LNCS, Springer-Verlag GmbH and Co. KG, pp. 1-12, 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russian Federation, 01.07.2019. https://doi.org/10.1007/978-3-030-19955-5_1

APA

Alhamdan, Y. M., & Kononov, A. (2019). Approximability and inapproximability for maximum k-edge-colored clustering problem. In R. van Bevern, & G. Kucherov (Eds.), Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings (pp. 1-12). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11532 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-19955-5_1

Vancouver

Alhamdan YM, Kononov A. Approximability and inapproximability for maximum k-edge-colored clustering problem. In van Bevern R, Kucherov G, editors, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 1-12. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-19955-5_1

Author

Alhamdan, Yousef M. ; Kononov, Alexander. / Approximability and inapproximability for maximum k-edge-colored clustering problem. Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. editor / René van Bevern ; Gregory Kucherov. Springer-Verlag GmbH and Co. KG, 2019. pp. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e0d50860ba3748918d2048b28b6a30aa,
title = "Approximability and inapproximability for maximum k-edge-colored clustering problem",
abstract = "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.",
keywords = "Clustering, Edge-colored graph, Randomized rounding, APPROXIMATION ALGORITHMS",
author = "Alhamdan, {Yousef M.} and Alexander Kononov",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-19955-5_1",
language = "English",
isbn = "9783030199548",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "1--12",
editor = "{van Bevern}, Ren{\'e} and Gregory Kucherov",
booktitle = "Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings",
address = "Germany",
note = "14th International Computer Science Symposium in Russia, CSR 2019 ; Conference date: 01-07-2019 Through 05-07-2019",

}

RIS

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