Hardness of set cover with intersection 1

DOI10.1007/3-540-45022-X_53MaRDI QIDQ2754182zbMATH OpenFDO

Authors V. S. Anil Kumar, Sunil Arya, H. Ramesh

Publication date 11 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45022-X_53

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A threshold of ln n for approximating set cover
• Nearly optimal NP-hardness of unique coverage
• Nearly optimal NP-hardness of unique coverage
• New and improved bounds for the minimum set cover problem
• \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point

Cited in

(27)

• Greedy domination on biclique-free graphs
• Maximum subset intersection
• Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
• Rainbow polygons for colored point sets in the plane
• Exact multi-covering problems with geometric sets
• Hypergraph representation via axis-aligned point-subspace cover
• Approximability of guarding weak visibility polygons
• On guarding the vertices of rectilinear domains
• On fair covering and hitting problems
• Bottleneck convex subsets: finding k large convex sets in a point set
• Identifying codes in hereditary classes of graphs and VC-dimension
• A parameterized algorithm for the hyperplane-cover problem
• Removing local extrema from imprecise terrains
• scientific article; zbMATH DE number 398939 (Why is no real title available?)
• Approximation algorithms for a geometric set cover problem
• Nearly optimal NP-hardness of unique coverage
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Nearly optimal NP-hardness of unique coverage
• Parameterized complexity of conflict-free set cover
• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• Minimum monotone tree decomposition of density functions defined on graphs
• Covering points by hyperplanes and related problems
• Parameterized covering in semi-ladder-free hypergraphs
• Approximate hypergraph vertex cover and generalized Tuza's conjecture
• Hypergraph representation via axis-aligned point-subspace cover
• On the approximability of covering points by lines and related problems

This page was built for publication: Hardness of set cover with intersection 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2754182)