Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
From MaRDI portal
Publication:5945918
DOI10.1007/s00453-001-0012-zzbMath0985.68089OpenAlexW2090022404MaRDI QIDQ5945918
Publication date: 19 February 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0012-z
Nonnumerical algorithms (68W05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Hardness of fully dense problems ⋮ Approximating vertex cover in dense hypergraphs ⋮ Connected Vertex Covers in Dense Graphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Connected vertex covers in dense graphs ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ Approximating edge dominating set in dense graphs ⋮ Approximating Subdense Instances of Covering Problems
This page was built for publication: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems