Maximum independent and disjoint coverage

Amit Kumar Dhar (), Raghunath Reddy Madireddy (), Supantha Pandit () and Jagpreet Singh ()
Additional contact information
Amit Kumar Dhar: Indian Institute of Technology Bhilai
Raghunath Reddy Madireddy: Bennett University
Supantha Pandit: Dhirubhai Ambani Institute of Information and Communication Technology
Jagpreet Singh: Indian Institute of Information Technology Allahabad

Journal of Combinatorial Optimization, 2020, vol. 39, issue 4, No 4, 1017-1037

Abstract: Abstract Set cover is one of the most studied optimization problems in Computer Science. In this paper, we target two interesting variations of this problem in a geometric setting: (i) maximum disjoint coverage (MDC), and (ii) maximum independent coverage (MIC) problems. In both problems, the input consists of a set P of points and a set O of geometric objects in the plane. The objective is to maximize the number of points covered by a set $$O'$$O′ of selected objects from O. In the MDC problem we restrict the objects in $$O'$$O′ are pairwise disjoint (non-intersecting). Whereas, in the MIC problem any pair of objects in $$O'$$O′ should not share a point from P (however, they may intersect each other). We consider various geometric objects as covering objects such as axis-parallel infinite lines, axis-parallel line segments, unit disks, axis-parallel unit squares, and intervals on a real line. For the covering objects axis-parallel infinite lines, we show that both MDC and MIC problems admit polynomial time algorithms. In addition to that, we give polynomial time algorithms for both MDC and MIC problems with intervals on the real line. On the other hand, we prove that the MIC problem is $${\mathsf {NP}}$$NP-complete when the objects are horizontal infinite lines and vertical segments. We also prove that both MDC and MIC problems are $${\mathsf {NP}}$$NP-complete for axis-parallel unit segments in the plane. For unit disks and axis-parallel unit squares, we prove that both these problems are $${\mathsf {NP}}$$NP-complete. Further, we present $${\mathsf {PTAS}}$$PTAS es for the MDC problem for unit disks as well as unit squares using Hochbaum and Maass’s “shifting strategy”. For unit squares, we design a $${\mathsf {PTAS}}$$PTAS for the MIC problem using Chan and Hu’s “mod-one transformation” technique.

Keywords: Set cover; Maximum coverage; Independent set; Disjoint coverage; $${\mathsf {NP}}$$ NP -hard; $${\mathsf {PTAS}}$$ PTAS; Line; Segment; Disk; Square (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00536-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00536-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00536-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().