2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence

DOI10.1007/978-3-030-40616-5_34MaRDI QIDQ5122316zbMATH OpenOpenAlexFDO

Authors Anna Panasenko, A. V. Kel'manov, S. A. Khamidullin

Publication date 22 September 2020

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-40616-5_34

zbMATH Keywords

approximation algorithmEuclidean spaceNP-hard problempolynomial timequadratic variationsequence of pointsweighted 2-partition

Mathematics Subject Classification ID

Numerical analysis (65-XX)

Cites work

• A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem
• A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train
• An approximating polynomial algorithm for a sequence partitioning problem
• An FPTAS for a vector subset search problem
• Clustering of time series data -- a survey
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• Exact pseudopolynomial algorithm for one sequence partitioning problem
• NP-hardness of some quadratic Euclidean 2-clustering problems
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence

Cited in

(1)

• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance

This page was built for publication: 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5122316)