2-Approximation Algorithm for Finding a Clique with Minimum Weight of Vertices and Edges / Eremin I. I.,Gimadi E. Kh,Kel'manov A. V.,Pyatkin A. V.,Khachai M. Yu // PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS. - 2014. - V. 284, l. 1. - P. S87-S95.

ISSN/EISSN:

0081-5438 / 1531-8605

Type:

Article

Abstract:

The problem of finding a minimum clique (with respect to the total weight of its vertices and edges) of fixed size in a complete undirected weighted graph is considered along with some of its important subclasses. Approximability issues are analyzed. The inapproximability of the problem is proved for the general case. A 2-approximation efficient algorithm with time complexity Omicron(n(2)) is suggested for the cases when vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some point configuration of Euclidean space.

Author keywords:

complete undirected graph; clique of fixed size; minimum weight of vertices and edges; subset search; approximability; polynomial time approximation algorithm; approximation guarantee; time complexity

DOI:

10.1134/S0081543814020084

Web of Science ID:

ISI:000334277400008

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	APR
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1531-8605
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	artem@math.nsc.ru gimadi@math.nsc.ru kelm@math.nsc.ru mkhachay@imm.uran.ru
ResearcherID-Numbers	Khachay, Michael/H-3251-2013 Kel'manov, Alexander/Q-9189-2016
ORCID-Numbers	Khachay, Michael/0000-0003-3555-0080 Kel'manov, Alexander/0000-0001-7757-7228
Funding-Acknowledgement	Russian Foundation for Basic Research {[}12-01-00090, 12-01-00093, 12-01-33028-mol-a-ved, 13-01-00210, 13-07-00070, 13-07-00181]; Ural and Siberian Branches of the Russian Academy of Sciences {[}12-P1-1016, 12-S1-1017/1, 7B]; Program for State Support of Leading Universities of the Russian Federation {[}02.A03.21.0006]
Funding-Text	This work was supported by the Russian Foundation for Basic Research (project nos. 12-01-00090, 12-01-00093, 12-01-33028-mol-a-ved, 13-01-00210, 13-07-00070, and 13-07-00181) and by integration projects of the Ural and Siberian Branches of the Russian Academy of Sciences (project nos. 12-P1-1016, 12-S1-1017/1, and 7B). The fifth author was also supported by the Program for State Support of Leading Universities of the Russian Federation (agreement no. 02.A03.21.0006 of August 27, 2013).
Number-of-Cited-References	6
Usage-Count-Since-2013	3
Journal-ISO	Proc. Steklov Inst. Math.
Doc-Delivery-Number	AE8UG