{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T23:06:07Z","timestamp":1754262367739,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_28","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"421-435","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Hardness Results and Approximation Schemes for Discrete Packing and Domination Problems"],"prefix":"10.1007","author":[{"given":"Raghunath Reddy","family":"Madireddy","sequence":"first","affiliation":[]},{"given":"Apurva","family":"Mudgal","sequence":"additional","affiliation":[]},{"given":"Supantha","family":"Pandit","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"28_CR1","first-page":"645","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Anna Adamaszek","year":"2013","unstructured":"Adamaszek, A., Wiese, A.: A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In: Symposium on Discrete Algorithms SODA, pp. 645\u2013656 (2014)"},{"issue":"1","key":"28_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-642-36065-7_10","volume-title":"WALCOM: Algorithms and Computation","author":"R Aschner","year":"2013","unstructured":"Aschner, R., Katz, M.J., Morgenstern, G., Yuditsky, Y.: Approximation schemes for covering and packing. In: Ghosh, S.K., Tokuyama, T. (eds.) WALCOM 2013. LNCS, vol. 7748, pp. 89\u2013100. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36065-7_10"},{"issue":"3","key":"28_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams\u2014a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"key":"28_CR5","unstructured":"Bandyapadhyay, S., Maheshwari, A., Mehrabi, S., Suri, S.: Approximating dominating set on intersection graphs of rectangles and L-frames. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, 27\u201331 August 2018, pp. 37:1\u201337:15 (2018)"},{"issue":"2","key":"28_CR6","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.comgeo.2012.04.001","volume":"47","author":"TM Chan","year":"2014","unstructured":"Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. 47(2), 112\u2013124 (2014)","journal-title":"Comput. Geom."},{"issue":"2","key":"28_CR7","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom. 48(2), 373\u2013392 (2012)","journal-title":"Discret. Comput. Geom."},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Ene, A.: On approximating maximum independent set of rectangles. In: Symposium on Foundations of Computer Science, FOCS, pp. 820\u2013829 (2016)","DOI":"10.1109\/FOCS.2016.92"},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1), 165\u2013177 (1990)","journal-title":"Discret. Math."},{"issue":"3","key":"28_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.ipl.2014.11.002","volume":"115","author":"GK Das","year":"2015","unstructured":"Das, G.K., De, M., Kolay, S., Nandy, S.C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Inf. Process. Lett. 115(3), 439\u2013446 (2015)","journal-title":"Inf. Process. Lett."},{"key":"28_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/978-3-540-78773-0_64","volume-title":"LATIN 2008: Theoretical Informatics","author":"T Erlebach","year":"2008","unstructured":"Erlebach, T., van Leeuwen, E.J.: Domination in geometric intersection graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 747\u2013758. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_64"},{"issue":"3","key":"28_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2017.01.030","volume":"674","author":"R Fraser","year":"2017","unstructured":"Fraser, R., L\u00f2pez-Ortiz, A.: The within-strip discrete unit disk cover problem. Theor. Comput. Sci. 674, 99\u2013115 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"28_CR14","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M Garey","year":"1977","unstructured":"Garey, M., Johnson, D.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"28_CR16","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-15775-2_21","volume-title":"Algorithms \u2013 ESA 2010","author":"Matt Gibson","year":"2010","unstructured":"Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: breaking the $$\\log n$$ barrier. In: Algorithms - ESA 2010, pp. 243\u2013254 (2010)"},{"key":"28_CR17","unstructured":"Har-Peled, S.: Being fat and friendly is not enough. CoRR abs\/0908.2369 (2009)"},{"issue":"2","key":"28_CR18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt","year":"1998","unstructured":"Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"28_CR19","unstructured":"Madireddy, R.R., Mudgal, A.: Stabbing line segments with disks and related problems. In: Canadian Conference on Computational Geometry, CCCG, pp. 201\u2013207 (2016)"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ipl.2018.09.003","volume":"141","author":"RR Madireddy","year":"2019","unstructured":"Madireddy, R.R., Mudgal, A.: Approximability and hardness of geometric hitting set with axis-parallel rectangles. Inf. Process. Lett. 141, 9\u201315 (2019)","journal-title":"Inf. Process. Lett."},{"key":"28_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-46515-7_16","volume-title":"Discrete and Computational Geometry","author":"T Matsui","year":"2000","unstructured":"Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194\u2013200. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/978-3-540-46515-7_16"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-319-26626-8_10","volume-title":"Combinatorial Optimization and Applications","author":"A Mudgal","year":"2015","unstructured":"Mudgal, A., Pandit, S.: Covering, hitting, piercing and packing rectangles intersecting an inclined line. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 126\u2013137. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-26626-8_10"},{"issue":"4","key":"28_CR23","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discret. Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discret. Comput. Geom."},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.ipl.2017.07.007","volume":"127","author":"SC Nandy","year":"2017","unstructured":"Nandy, S.C., Pandit, S., Roy, S.: Faster approximation for maximum independent set on unit disk graph. Inf. Process. Lett. 127, 58\u201361 (2017)","journal-title":"Inf. Process. Lett."},{"key":"28_CR25","unstructured":"Pandit, S.: Dominating set of rectangles intersecting a straight line. In: Canadian Conference on Computational Geometry CCCG, pp. 144\u2013149 (2017)"},{"issue":"3","key":"28_CR26","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"Wan, P., Xu, X., Wang, Z.: Wireless coverage with disparate ranges. In: Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc, p. 11 (2011)","DOI":"10.1145\/2107502.2107517"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:50:02Z","timestamp":1710345002000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}