Lower bounds for covering problems

DOI10.1023/A:1015670603203MaRDI QIDQ1868261zbMATH OpenOpenAlexFDO

Authors Michael Segal

Publication date 27 April 2003

Published in JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1015670603203

zbMATH Keywords

lower boundsmax-gap problemreduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Recommendations

• Covering a Set of Points with a Minimum Number of Lines
• Covering a Point Set by Two Disjoint Rectangles
• Lower bounds for online bin covering-type problems
• On rectangular covering problems
• Lower bounds for maximal and convex layers problems

Cited in

(17)

• On bounds for a board covering problem
• Lower bounds for some decision problems over \(C\)
• Optimizing squares covering a set of points
• On the Hadwiger covering problem in low dimensions
• Minimum perimeter-sum partitions in the plane
• New lower bounds for multiple coverings
• A lower bound for the coverability problem in acyclic pushdown VAS
• Bounds for optimal coverings
• Optimizing squares covering a set of points
• Lower Bounds for Coin-Weighing Problems
• BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
• scientific article; zbMATH DE number 1504678 (Why is no real title available?)
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
• scientific article; zbMATH DE number 1855660 (Why is no real title available?)
• Square and Rectangle Covering with Outliers
• Covering points by disjoint boxes with outliers
• Lower bounds for coverings of pairs by large blocks

This page was built for publication: Lower bounds for covering problems

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