Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem

DOI10.1007/978-3-030-58657-7_4MaRDI QIDQ4965097zbMATH OpenOpenAlexFDO

Authors Anna Panasenko, Vladimir Khandeev

Publication date 25 February 2021

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-58657-7_4

zbMATH Keywords

exact algorithmEuclidean spacepolynomial-timeNP-hard problemone-dimensional caseweighted clusteringminimum sum-of-squares

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• A PTAS for one Cardinality-Weighted 2-Clustering problem
• On polynomial solvability of one quadratic Euclidean clustering problem on a line
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem

Cites work

• A PTAS for one Cardinality-Weighted 2-Clustering problem
• A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem
• An introduction to statistical learning. With applications in R
• Cluster Analysis and Mathematical Programming
• Data mining. The textbook
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• NP-hardness of some quadratic Euclidean 2-clustering problems
• On the complexity of some quadratic Euclidean 2-clustering problems
• PRMLT
• Pattern recognition and machine learning.
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center

Cited in

(5)

• On polynomial solvability of one quadratic Euclidean clustering problem on a line
• A PTAS for one Cardinality-Weighted 2-Clustering problem
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• An algorithm and a core set result for the weighted Euclidean one-center problem

Describes a project that uses

Uses Software

• ElemStatLearn
• PRMLT

This page was built for publication: Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem

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