Easy NP-hardness Proofs of Some Subset Choice Problems
From MaRDI portal
Publication:4965101
DOI10.1007/978-3-030-58657-7_8zbMATH Open1460.90156OpenAlexW3085196264MaRDI QIDQ4965101FDOQ4965101
Authors: Artem Pyatkin 
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
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
Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- NP-hardness of Euclidean sum-of-squares clustering
- On Grouping for Maximum Homogeneity
- Title not available (Why is that?)
- Title not available (Why is that?)
- The planar \(k\)-means problem is NP-hard
- A 2-approximation polynomial algorithm for a clustering problem
- Finding k points with minimum diameter and related problems
- A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
- The problem of finding a subset of vectors with maximal total weight
- On the complexity of a search for a subset of ``similar vectors
- An approximation scheme for a problem of search for a vector subset
- A Polynomial Time Algorithm for Shaped Partition Problems
- Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
- 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
- Efficient randomized algorithm for a vector subset problem
- Complexity and approximation of finding the longest vector sum
- An exact algorithm for finding a vector subset with the longest sum
- An FPTAS for a vector subset search problem
- Solving some vector subset problems by Voronoi diagrams
- Maximum diversity problem with squared Euclidean distance
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)
