RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2014 Volume 21, Issue 3, Pages 41–52 (Mi da774)

This article is cited in 34 papers

FPTAS for solving a problem of search for a vector subset

A. V. Kel'manovab, S. M. Romanchenkoab

a S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia

Abstract: We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P$=$NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented. Bibliogr. 12.

Keywords: search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.

UDC: 519.16+519.85

Received: 11.11.2013
Revised: 29.01.2014


 English version:
Journal of Applied and Industrial Mathematics, 2014, 8:3, 329–336

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024