An approximating polynomial algorithm for a sequence partitioning problem

DOI10.1134/S1990478914020100zbMATH Open1324.68243OpenAlexW2109886072MaRDI QIDQ5264726FDOQ5264726

A. V. Kel'manov, S. A. Khamidullin

Publication date: 27 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478914020100

zbMATH Keywords

clusteringNP-hardnessminimum sum-of-squared distancesEuclidean vector sequencepolynomial 2-approximation algorithm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (7)

• Multilevel polynomial partitions and simplified range searching
• Title not available (Why is that?)
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence
• A randomized algorithm for a sequence 2-clustering problem
• An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

This page was built for publication: An approximating polynomial algorithm for a sequence partitioning problem

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