Easy NP-hardness Proofs of Some Subset Choice Problems
From MaRDI portal
Publication:4965101
Recommendations
- NP-completeness of some problems of a vectors subset choice
- On universally easy classes for NP-complete problems
- On universally easy classes for NP-complete problems.
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- On the complexity of certain problems of choosing subset of vectors
- Hardness results for the subpower membership problem
- The hardness of solving subset sum with preprocessing
- scientific article; zbMATH DE number 1775419
- A generic approach to proving NP-hardness of partition type problems
- An alternative approach for proving the NP-hardness of optimization problems
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3340881 (Why is no real title available?)
- A 2-approximation polynomial algorithm for a clustering problem
- A Polynomial Time Algorithm for Shaped Partition Problems
- A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
- An FPTAS for a vector subset search problem
- An approximation scheme for a problem of search for a vector subset
- An exact algorithm for finding a vector subset with the longest sum
- Complexity and approximation of finding the longest vector sum
- Efficient randomized algorithm for a vector subset problem
- Finding k points with minimum diameter and related problems
- Maximum diversity problem with squared Euclidean distance
- NP-hardness of Euclidean sum-of-squares clustering
- NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
- On Grouping for Maximum Homogeneity
- On the complexity of a search for a subset of ``similar vectors
- On the complexity of some quadratic Euclidean 2-clustering problems
- Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
- Solving some vector subset problems by Voronoi diagrams
- The planar \(k\)-means problem is NP-hard
- The problem of finding a subset of vectors with maximal total weight
Cited in
(5)- On the complexity of certain problems of choosing subset of vectors
- NP-completeness of some problems of a vectors subset choice
- A simple proof that the \((n^{2} - 1)\)-puzzle is hard
- On complexity of the problem of choosing a vector subset with maximal sum length
- The problem of finding a subset of vectors with maximal total weight
This page was built for publication: Easy NP-hardness Proofs of Some Subset Choice Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4965101)
