Easy NP-hardness Proofs of Some Subset Choice Problems
From MaRDI portal
Publication:4965101
DOI10.1007/978-3-030-58657-7_8zbMath1460.90156OpenAlexW3085196264MaRDI QIDQ4965101
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_8
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The planar \(k\)-means problem is NP-hard
- On the complexity of a search for a subset of ``similar vectors
- NP-hardness of Euclidean sum-of-squares clustering
- Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
- Complexity and approximation of finding the longest vector sum
- Maximum diversity problem with squared Euclidean distance
- NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
- On the complexity of some quadratic Euclidean 2-clustering problems
- Solving some vector subset problems by Voronoi diagrams
- Efficient Randomized Algorithm for a Vector Subset Problem
- Finding k points with minimum diameter and related problems
- On Grouping for Maximum Homogeneity
- A Polynomial Time Algorithm for Shaped Partition Problems
- An approximation scheme for a problem of search for a vector subset
- A 2-approximation polynomial algorithm for a clustering problem
- An FPTAS for a vector subset search problem
- An exact algorithm for finding a vector subset with the longest sum
This page was built for publication: Easy NP-hardness Proofs of Some Subset Choice Problems
