Approximation algorithms for some intractable problems of choosing a vector subsequence

被引：0

作者：

Kel'manov, A.V. ^{[1
,2
]}

Romanchenko, S.M. ^{[1
]}

Khamidullin, S.A. ^{[1
]}

机构：

[1] Sobolev Institute of Mathematics, Novosibirsk, 630090

[2] Novosibirsk State University, Novosibirsk, 630090

来源：

Journal of Applied and Industrial Mathematics | 2012年 / 6卷 / 04期

基金：

俄罗斯基础研究基金会;

关键词：

cluster analysis; efficient approximation algorithm; minimum sum of squares of distances; NP-hardness; search for a vector subset;

D O I：

10.1134/S1990478912040059

中图分类号：

学科分类号：

摘要：

We consider some intractable optimization problems of finding a subsequence in a finite sequence of vectors of the Euclidean space. We assume that the sought subsequence contains a fixed number of vectors close to each other under the criterion of the minimum sum of the squares of distances. Moreoveer, this subsequence has to satisfy the following condition: the difference between the indexes of each previous and next vectors of the sought subsequence is bounded with lower and upper constants. Some 2-approximation efficient algorithms for solving these problems are introduced. © 2012 Pleiades Publishing, Ltd.

引用

页码：443 / 450

页数：7

共 12 条

[1] NP-completeness of some problems of choosing a vector subset [J].

Kel'manov A.V. ;

Pyatkin A.V. .

Journal of Applied and Industrial Mathematics, 2011, 5 (3) :352-357

[2] Efficient Approximation Algorithms for Some NP-hard Problems of Partitioning a Set and a Sequence [J].

Kel'manov, Alexander .

2017 INTERNATIONAL MULTI-CONFERENCE ON ENGINEERING, COMPUTER AND INFORMATION SCIENCES (SIBIRCON), 2017, :87-90

[3] Approximation Algorithms for Certain Network Improvement Problems [J].

Sven O. Krumke ;

Madhav V. Marathe ;

Hartmut Noltemeier ;

R. Ravi ;

S. S. Ravi .

Journal of Combinatorial Optimization, 1998, 2 :257-288

[4] Approximation algorithms for certain network improvement problems [J].

Krumke, SO ;

Marathe, MV ;

Noltemeier, H ;

Ravi, R ;

Ravi, SS .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 1998, 2 (03) :257-288

[5] Exact Algorithms for Two Quadratic Euclidean Problems of Searching for the Largest Subset and Longest Subsequence [J].

Kel'manov, Alexander ;

Khamidullin, Sergey ;

Khandeev, Vladimir ;

Pyatkin, Artem .

LEARNING AND INTELLIGENT OPTIMIZATION, LION 12, 2019, 11353 :326-336

[6] Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence [J].

Kel'manov, Alexander ;

Khamidullin, Sergey ;

Khandeev, Vladimir ;

Pyatkin, Artem .

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2020, 88 (1-3) :157-168

[7] Polynomial time approximation schemes for some dense instances of NP-hard optimization problems [J].

Karpinski, M .

ALGORITHMICA, 2001, 30 (03) :386-397

[8] Applying non-hierarchical cluster analysis algorithms to climate classification: Some problems and their solution [J].

Gerstengarbe, FW ;

Werner, PC ;

Fraedrich, K .

THEORETICAL AND APPLIED CLIMATOLOGY, 1999, 64 (3-4) :143-150

[9] Applying Non-Hierarchical Cluster Analysis Algorithms to Climate Classification: Some Problems and their Solution [J].

F.-W. Gerstengarbe ;

P. C. Werner ;

K. Fraedrich .

Theoretical and Applied Climatology, 1999, 64 :143-150

[10] Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space [J].

Kel'manov, A. V. ;

Panasenko, A. V. ;

Khandeev, V. I. .

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 2019, 59 (05) :842-850

← 1 2 →