On the geometric red-blue set cover problem

DOI10.1007/978-3-030-68211-8_11OpenAlexW3132605018MaRDI QIDQ2232240

Subhas C. Nandy, Supantha Pandit, Raghunath Reddy Madireddy

Publication date: 4 October 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-68211-8_11

zbMATH Keywords

polynomial time algorithmssegmentsred-blue set coveranchored rectangles\( \mathsf{NP} \)-hard\( \mathsf{APX} \)-hardspecial red-blue set cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Exact algorithms and hardness results for geometric red-blue hitting set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• The class cover problem with boxes
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
• Geometric red-blue set cover for unit squares and related problems
• A PTAS for the Weighted Unit Disk Cover Problem
• Optimal Binary Space Partitions in the Plane
• PTAS for Weighted Set Cover on Unit Squares
• On the hardness of approximating minimization problems
• Reducibility among Combinatorial Problems
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Maximum independent and disjoint coverage

This page was built for publication: On the geometric red-blue set cover problem