Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1263204
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- On the efficiency of polynomial time approximation schemes
- Hardness of fully dense problems
Cited in
(17)- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- Connected Vertex Covers in Dense Graphs
- Connected vertex covers in dense graphs
- On the efficiency of polynomial time approximation schemes
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Exploiting dense structures in parameterized complexity
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- Theory and Applications of Models of Computation
- Approximating subdense instances of covering problems
- Approximating edge dominating set in dense graphs
- Hardness of fully dense problems
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
- Approximating edge dominating set in dense graphs
- Polynomially bounded minimization problems which are hard to approximate
- Approximating vertex cover in dense hypergraphs
- Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
This page was built for publication: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5945918)
