A constant-factor approximation algorithm for red-blue set cover with unit disks

DOI10.1007/978-3-030-80879-2_14OpenAlexW3185746738MaRDI QIDQ5918633

Apurva Mudgal, Raghunath Reddy Madireddy

Publication date: 22 March 2022

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-80879-2_14

zbMATH Keywords

sweep-line methodunit disksred-blue set coverline-separablestrip-separable

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (1)

A constant-factor approximation algorithm for red-blue set cover with unit disks

Cites Work

• Unnamed Item
• Unit disk cover problem in 2D
• The within-strip discrete unit disk cover problem
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• Geometric red-blue set cover for unit squares and related problems
• On the Discrete Unit Disk Cover Problem
• A PTAS for the Weighted Unit Disk Cover Problem
• PTAS for Weighted Set Cover on Unit Squares
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Covering Points by Unit Disks of Fixed Location

This page was built for publication: A constant-factor approximation algorithm for red-blue set cover with unit disks