Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions

被引：2
作者：
Mudgal, Apurva [1 ]
Pandit, Supantha [1 ]
机构：
[1] Indian Inst Technol Ropar, Dept Comp Sci & Engn, Nangal Rd, Rupnagar 140001, Punjab, India
来源：
DISCRETE APPLIED MATHEMATICS | 2016年 / 211卷
关键词：
Geometric set cover; Geometric hitting set; Generalized class cover; Half-strips; Opposite directions; NP-complete; APPROXIMATION ALGORITHMS;
D O I：
10.1016/j.dam.2016.03.006
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We show that hitting set and set cover problems with half-strips oriented in two opposite directions are NP-complete. Further, we prove that two variations of the generalized class cover problem on half-strips oriented in two opposite directions are NP-complete, thus resolving two open problems we posed in Mudgal and Pandit (2014) [12]. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：143 / 162
页数：20
相关论文
共 15 条
  • [1] THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM
    BALAS, E
    [J]. NETWORKS, 1989, 19 (06) : 621 - 636
  • [2] Visibility preserving terrain simplification - An experimental study
    Ben-Moshe, B
    Katz, MJ
    Mitchell, JSB
    Nir, Y
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 28 (2-3): : 175 - 190
  • [3] The class cover problem with boxes
    Bereg, S.
    Cabello, S.
    Diaz-Banez, J. M.
    Perez-Lantero, P.
    Seara, C.
    Ventura, I.
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2012, 45 (07): : 294 - 304
  • [4] Approximation algorithms for the class cover problem
    Cannon, AH
    Cowen, LJ
    [J]. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2004, 40 (3-4) : 215 - 223
  • [5] Chakrabarty D, 2010, LECT NOTES COMPUT SC, V6080, P355, DOI 10.1007/978-3-642-13036-6_27
  • [6] Exact algorithms and APX-hardness results for geometric packing and covering problems
    Chan, Timothy M.
    Grant, Elyot
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (02): : 112 - 124
  • [7] Chin FYL, 2009, LECT NOTES COMPUT SC, V5573, P145, DOI 10.1007/978-3-642-02026-1_13
  • [8] APPROXIMATION ALGORITHMS FOR HITTING OBJECTS WITH STRAIGHT-LINES
    HASSIN, R
    MEGIDDO, N
    [J]. DISCRETE APPLIED MATHEMATICS, 1991, 30 (01) : 29 - 42
  • [9] Orthogonal segment stabbing
    Katz, MJ
    Mitchell, JSB
    Nir, Y
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2005, 30 (02): : 197 - 205
  • [10] THE PROBLEM OF COMPATIBLE REPRESENTATIVES
    KNUTH, DE
    RAGHUNATHAN, A
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) : 422 - 427
12