Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

Abstract

The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size such that the sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) does not exceed a given percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence under the same restriction on the sum of squared distances as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

Original languageEnglish
Title of host publicationLearning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages326-336
Number of pages11
ISBN (Print)9783030053475
DOIs
Publication statusPublished - 1 Jan 2019
Event12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Greece
Duration: 10 Jun 201815 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11353 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Learning and Intelligent Optimization, LION 12
CountryGreece
CityKalamata
Period10.06.201815.06.2018

Keywords

  • Euclidean space
  • Exact algorithm
  • Fixed space dimension
  • Integer coordinates
  • Largest set
  • Longest subsequence
  • NP-hard problem
  • Pseudopolynomial time
  • Quadratic variation

Fingerprint

Dive into the research topics of 'Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence'. Together they form a unique fingerprint.

Cite this