Polynomial-Time Approximation Scheme for a Problem of Searching for the Largest Subset with the Constraint on Quadratic Variation

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

Abstract

The paper is addressed to one strongly NP-hard problem of searching for the largest subset in the finite set of points in Euclidean space. A restriction is imposed on the searched subset: quadratic variation of its points with respect to the unknown centroid of this subset must not exceed a given value. We present the first polynomial-time approximation scheme for this problem.

Original languageEnglish
Title of host publicationNumerical Computations
Subtitle of host publicationTheory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers
EditorsYaroslav D. Sergeyev, Dmitri E. Kvasov
PublisherSpringer Gabler
Pages400-405
Number of pages6
ISBN (Print)9783030406158
DOIs
Publication statusPublished - 1 Jan 2020
Event3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 - Crotone, Italy
Duration: 15 Jun 201921 Jun 2019

Publication series

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

Conference

Conference3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
CountryItaly
CityCrotone
Period15.06.201921.06.2019

Keywords

  • Euclidean space
  • Largest subset
  • NP-hard problem
  • Polynomial-time approximation scheme
  • Quadratic variation

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'Polynomial-Time Approximation Scheme for a Problem of Searching for the Largest Subset with the Constraint on Quadratic Variation'. Together they form a unique fingerprint.

Cite this