{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:14:53Z","timestamp":1710202493021},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T00:00:00Z","timestamp":1701043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T00:00:00Z","timestamp":1701043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00454-023-00608-8","type":"journal-article","created":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T22:01:38Z","timestamp":1701122498000},"page":"787-822","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Geometric Stabbing via Threshold Rounding and Factor Revealing LPs"],"prefix":"10.1007","volume":"71","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Saurabh","family":"Ray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,27]]},"reference":[{"key":"608_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201914, pp. 645\u2013656 (2014)","DOI":"10.1137\/1.9781611973402.49"},{"key":"608_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS \u201913, pp. 400\u2013409, Washington. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"608_CR3","doi-asserted-by":"crossref","unstructured":"Aschner, R. Katz, M.J., Morgenstern, G., Yuditsky, Y.: Approximation schemes for covering and packing. In: WALCOM: Algorithms and Computation. volume 7748 of Lecture Notes in Computer Science, pp. 89\u2013100. Springer, Berlin Heidelberg (2013)","DOI":"10.1007\/978-3-642-36065-7_10"},{"issue":"1","key":"608_CR4","first-page":"221","volume":"7","author":"Nikhil Bansal","year":"2016","unstructured":"Bansal, Nikhil, Pruhs, Kirk: Weighted geometric set multi-cover via quasi-uniform sampling. JoCG 7(1), 221\u2013236 (2016)","journal-title":"JoCG"},{"key":"608_CR5","doi-asserted-by":"crossref","unstructured":"Basu\u00a0Roy, A., Govindarajan, S., Raman, R., Ray, S.: Packing and covering with non-piercing regions. Discrete Comput. Geom. (2018)","DOI":"10.1007\/s00454-018-9983-2"},{"key":"608_CR6","unstructured":"Ben-David, S., Grant, E., Ma, W., Sharpe, M.: The approximability and integrality gap of interval stabbing and independence problems. In: Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, Prince Edward Island, August 8\u201310, 2012, pp. 47\u201352 (2012)"},{"issue":"4","key":"608_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite vc-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"608_CR8","unstructured":"Caoduro, M., Cslovjecsek, J., Pilipczuk, M., Wegrzycki, K.: Independence number of intersection graphs of axis-parallel segments. CoRR, abs\/2205.15189 (2022)"},{"key":"608_CR9","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u2013 13, 2021, pp. 860\u2013868. SIAM (2021)","DOI":"10.1137\/1.9781611976465.54"},{"key":"608_CR10","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u2013 13, 2021, pp. 860\u2013868. SIAM (2021)","DOI":"10.1137\/1.9781611976465.54"},{"key":"608_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912, pp. 1576\u20131585 (2012)","DOI":"10.1137\/1.9781611973099.125"},{"key":"608_CR12","unstructured":"Chan, T.M., van Dijk, T.C., Fleszar, K., Spoerhase, J., Wolff, A.: Stabbing rectangles by line segments\u2014how decomposition reduces the shallow-cell complexity. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16\u201319, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pp. 61:1\u201361:13. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum f\u00fcr Informatik (2018)"},{"key":"608_CR13","unstructured":"Chan, T.M.: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In: Symposuim on Computational Geometry 2012, SoCG \u201912, Chapel Hill, June 17\u201320, 2012, pp. 293\u2013302. ACM (2012)"},{"issue":"2","key":"608_CR14","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. Discrete Comput. Geom. 48(2), 373\u2013392 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"608_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms 9, 1\u20139 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"1\u20132","key":"608_CR16","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s00453-010-9471-4","volume":"62","author":"M Dom","year":"2012","unstructured":"Dom, M., Fellows, M.R., Rosamond, F.A., Sikdar, S.: The parameterized complexity of stabbing rectangles. Algorithmica 62(1\u20132), 564\u2013594 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"608_CR17","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1367064.1367074","volume":"4","author":"G Even","year":"2008","unstructured":"Even, G., Levi, R., Rawitz, D., Schieber, B., Shahar, S., Sviridenko, M.: Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Trans. Algorithms 4(3), 34\u201337 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"608_CR18","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/s00224-016-9744-7","volume":"62","author":"SP Fekete","year":"2018","unstructured":"Fekete, S.P., Huang, K., Mitchell, J.S.B., Parekh, O., Phillips, C.A.: Geometric hitting set for segments of few orientations. Theory Comput. Syst. 62(2), 268\u2013303 (2018)","journal-title":"Theory Comput. Syst."},{"key":"608_CR19","unstructured":"G\u00e1lvez, W., Khan, A., Mari, M., M\u00f6mke, T., Pittu, M.R., Wiese, A.: A 4-approximation algorithm for maximum independent set of rectangles. CoRR, abs\/2106.00623 (2021)"},{"issue":"22","key":"608_CR20","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","volume":"307","author":"F Gardi","year":"2007","unstructured":"Gardi, F.: The Roberts characterization of proper and unit interval graphs. Discrete Math. 307(22), 2906\u20132908 (2007)","journal-title":"Discrete Math."},{"issue":"1","key":"608_CR21","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jagm.2002.1221","volume":"43","author":"DR Gaur","year":"2002","unstructured":"Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. J. Algorithms 43(1), 138\u2013152 (2002)","journal-title":"J. Algorithms"},{"key":"608_CR22","doi-asserted-by":"crossref","unstructured":"Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: Breaking the $$\\log n$$ barrier. In: Algorithms\u2014ESA 2010-18th Annual European Symposium, Liverpool, United Kingdom, September 6\u20138, 2010, Proceedings, pp. 243\u2013254 (2010)","DOI":"10.1007\/978-3-642-15775-2_21"},{"issue":"3","key":"608_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(87)90012-5","volume":"8","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Maass, W.: Fast approximation algorithms for a nonconvex covering problem. J. Algorithms 8(3), 305\u2013323 (1987)","journal-title":"J. Algorithms"},{"key":"608_CR24","doi-asserted-by":"crossref","unstructured":"Kovaleva, S., Spieksma, F.C.R.: Approximation of rectangle stabbing and interval stabbing problems. In: Algorithms\u2014ESA 2004, pp. 426\u2013435. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30140-0_39"},{"issue":"3","key":"608_CR25","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1137\/S089548010444273X","volume":"20","author":"S Kovaleva","year":"2006","unstructured":"Kovaleva, S., Spieksma, F.C.R.: Approximation algorithms for rectangle stabbing and interval stabbing problems. SIAM J. Discrete Math. 20(3), 748\u2013768 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"608_CR26","unstructured":"Mitchell, J.S.B.: Approximating maximum independent set for rectangles in the plane. CoRR, abs\/2101.00326 (2021)"},{"issue":"4","key":"608_CR27","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. Discrete Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"608_CR28","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1137\/14099317X","volume":"44","author":"NH Mustafa","year":"2015","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM J. Comput. 44(6), 1650\u20131669 (2015)","journal-title":"SIAM J. Comput."},{"key":"608_CR29","unstructured":"Raman, R., Ray, S.: Planar support for non-piercing regions and applications. In: 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pp. 69:1\u201369:14 (2018)"},{"key":"608_CR30","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 641\u2013648 (2010)","DOI":"10.1145\/1806689.1806777"},{"key":"608_CR31","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00224-005-1273-8","volume":"40","author":"G Xu","year":"2005","unstructured":"Xu, G., Xu, J.: Constant approximation algorithms for rectangle stabbing and related problems. Theory Comput. Syst. 40, 187\u2013204 (2005)","journal-title":"Theory Comput. Syst."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00608-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00608-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00608-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T15:12:30Z","timestamp":1710169950000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00608-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,27]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["608"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00608-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,27]]},"assertion":[{"value":"9 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}