TY - GEN
T1 - Minimum Membership Covering and Hitting
AU - Mitchell, Joseph S.B.
AU - Pandit, Supantha
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Set cover is a well-studied problem with application in many fields. A well-known variation of this problem is the Minimum Membership Set Cover problem. In this problem, given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem. In this problem, given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variations in a geometric setting with various types of geometric objects in the plane, including axis-parallel line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares at least one boundary edge (top or bottom) with one of the input horizontal lines). For each of these problems either we prove NP-hardness or design a polynomial-time algorithm. More precisely, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. We also provide approximation algorithms for some of the problems. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.
AB - Set cover is a well-studied problem with application in many fields. A well-known variation of this problem is the Minimum Membership Set Cover problem. In this problem, given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem. In this problem, given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variations in a geometric setting with various types of geometric objects in the plane, including axis-parallel line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares at least one boundary edge (top or bottom) with one of the input horizontal lines). For each of these problems either we prove NP-hardness or design a polynomial-time algorithm. More precisely, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. We also provide approximation algorithms for some of the problems. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.
KW - Depth of a point
KW - Minimum Membership Hitting Set
KW - Minimum Membership Set Cover
KW - NP-hard
KW - Rectangles
KW - Segments
KW - Strips
UR - https://www.scopus.com/pages/publications/85062672548
U2 - 10.1007/978-3-030-10564-8_31
DO - 10.1007/978-3-030-10564-8_31
M3 - Conference contribution
AN - SCOPUS:85062672548
SN - 9783030105631
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 394
EP - 406
BT - WALCOM
A2 - Nakano, Shin-ichi
A2 - Mukhopadhyaya, Krishnendu
A2 - Das, Gautam K.
A2 - Mandal, Partha S.
PB - Springer Verlag
T2 - 13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019
Y2 - 27 February 2019 through 2 March 2019
ER -