{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T20:40:03Z","timestamp":1732221603286,"version":"3.28.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"SERB Core Research Grant","award":["CRG\/2022\/001176"]},{"name":"Pratiksha Trust Young Investigator Award"},{"name":"Google ExploreCS Award"},{"name":"Google India Research Award"},{"name":"Kotak IISc AI-ML Center (KIAC) PhD fellowship"},{"name":"Walmart Center for Tech Excellence"},{"name":"Walmart Center for Tech Excellence"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10107-024-02106-y","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T15:03:15Z","timestamp":1718290995000},"page":"607-630","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A PTAS for the horizontal rectangle stabbing problem"],"prefix":"10.1007","volume":"206","author":[{"given":"Arindam","family":"Khan","sequence":"first","affiliation":[]},{"given":"Aditya","family":"Subramanian","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"key":"2106_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOCS, pp. 400\u2013409 (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"2106_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Chang, H., Suri, S., Xiao, A., Xue, J.: Dynamic geometric set cover and hitting set. ACM Trans. Algorithms 18(4), 40:1\u201340:37 (2022)","DOI":"10.1145\/3551639"},{"issue":"7","key":"2106_CR3","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size $$\\varepsilon $$-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"2106_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: SODA, pp. 13\u201325 (2014)","DOI":"10.1137\/1.9781611973402.2"},{"issue":"5","key":"2106_CR5","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1137\/130911317","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. SIAM J. Comput. 43(5), 1684\u20131698 (2014)","journal-title":"SIAM J. Comput."},{"key":"2106_CR6","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Marchetti-Spaccamela, A., Vitaletti, A., Korteweg, P., Skutella, M., Stougie, L.: Latency-constrained aggregation in sensor networks. ACM Trans. Algorithms 6(1), 13:1\u201313:20 (2009)","DOI":"10.1145\/1644015.1644028"},{"issue":"4","key":"2106_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":"2106_CR8","unstructured":"Chan, T.M., van Dijk, T.C., Fleszar, K., Spoerhase, J., Wolff, A.: Stabbing rectangles by line segments: how decomposition reduces the shallow-cell complexity. In: ISAAC, pp. 61:1\u201361:13 (2018)"},{"issue":"2","key":"2106_CR9","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."},{"key":"2106_CR10","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: SODA, pp. 1576\u20131585. SIAM (2012)","DOI":"10.1137\/1.9781611973099.125"},{"key":"2106_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., He, Q., Suri, S., Xue, J.: Dynamic geometric set cover, revisited. In: SODA, pp. 3496\u20133528. SIAM (2022)","DOI":"10.1137\/1.9781611977073.139"},{"key":"2106_CR12","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"issue":"3","key":"2106_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"2106_CR14","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1007\/s00453-017-0298-0","volume":"80","author":"A Das","year":"2018","unstructured":"Das, A., Fleszar, K., Kobourov, S.G., Spoerhase, J., Veeramoni, S., Wolff, A.: Approximating the generalized minimum manhattan network problem. Algorithmica 80(4), 1170\u20131190 (2018)","journal-title":"Algorithmica"},{"key":"2106_CR15","unstructured":"Deppert, M.A., Jansen, K., Khan, A., Rau, M., Tutas, M.: Peak demand minimization via sliced strip packing. In: APPROX\/RANDOM, pp. 21:1\u201321:24 (2021)"},{"key":"2106_CR16","unstructured":"Eisenbrand, F., Gallato, M., Svensson, O., Venzin, M.: A QPTAS for stabbing rectangles. CoRR arxiv:2107.06571 (2021)"},{"issue":"5","key":"2106_CR17","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.dam.2006.03.039","volume":"156","author":"G Finke","year":"2008","unstructured":"Finke, G., Jost, V., Queyranne, M., Seb\u00f6, A.: Batch processing with interval graph compatibilities between tasks. Discrete Appl. Math. 156(5), 556\u2013568 (2008)","journal-title":"Discrete Appl. Math."},{"key":"2106_CR18","unstructured":"G\u00e1lvez, W., Grandoni, F., Ameli, A.J., Jansen, K., Khan, A., Rau, M.: A tight (3\/2+$$\\epsilon $$) approximation for skewed strip packing. In: APPROX\/RANDOM, pp. 44:1\u201344:18 (2020)"},{"key":"2106_CR19","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Heydrich, S., Ingala, S., Khan, A., Wiese, A.: Approximating geometric knapsack via l-packings. In: FOCS, pp. 260\u2013271 (2017)","DOI":"10.1109\/FOCS.2017.32"},{"key":"2106_CR20","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Khan, A., Ram\u00edrez-Romero, D., Wiese, A.: Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more. In: SoCG, pp. 39:1\u201339:17 (2021)","DOI":"10.1145\/3473713"},{"key":"2106_CR21","unstructured":"G\u00e1lvez, W., Khan, A., Mari, M., M\u00f6mke, T., Pittu, M.R., Wiese, A.: A (2+$$\\epsilon $$)-approximation algorithm for maximum independent set of rectangles. CoRR arxiv:2106.00623 (2021)"},{"issue":"1","key":"2106_CR22","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"},{"issue":"2","key":"2106_CR23","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.comgeo.2013.08.008","volume":"47","author":"R Harren","year":"2014","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A (5\/3 + $$\\epsilon $$)-approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014)","journal-title":"Comput. Geom."},{"issue":"1","key":"2106_CR24","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"2106_CR25","unstructured":"Jansen, K., Khan, A., Lira, M., Sreenivas, K.V.N.: A PTAS for packing hypercubes into a knapsack. In: ICALP, pp. 78:1\u201378:20 (2022)"},{"key":"2106_CR26","unstructured":"Kar, D., Khan, A., Wiese, A.: Approximation algorithms for round-ufp and round-sap. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) ESA, pp. 71:1\u201371:19 (2022)"},{"key":"2106_CR27","unstructured":"Khan, A., Lonkar, A., Maiti, A., Sharma, A., Wiese, A.: Tight approximation algorithms for two-dimensional guillotine strip packing. In: ICALP, pp. 80:1\u201380:20 (2022)"},{"key":"2106_CR28","unstructured":"Khan, A., Lonkar, A., Rahul, S., Subramanian, A., Wiese, A.: Online and dynamic algorithms for geometric set cover and hitting set. In: SoCG, pp. 46:1\u201346:17 (2023)"},{"key":"2106_CR29","doi-asserted-by":"crossref","unstructured":"Khan, A., Maiti, A., Sharma, A., Wiese, A.: On guillotine separable packings for the two-dimensional geometric knapsack problem. In: SoCG, pp. 48:1\u201348:17 (2021)","DOI":"10.1145\/3473713"},{"key":"2106_CR30","unstructured":"Khan, A., Pittu, M.R.: On guillotine separability of squares and rectangles. In: APPROX\/RANDOM, pp. 47:1\u201347:22 (2020)"},{"key":"2106_CR31","unstructured":"Khan, A., Sharma, E.: Tight approximation algorithms for geometric bin packing with skewed items. In: APPROX\/RANDOM, pp. 22:1\u201322:23 (2021)"},{"key":"2106_CR32","unstructured":"Khan, A., Sharma, E., Sreenivas, K.V.N.: Geometry meets vectors: approximation algorithms for multidimensional packing. In: FSTTCS, pp. 23:1\u201323:22 (2022)"},{"key":"2106_CR33","doi-asserted-by":"crossref","unstructured":"Khan, A., Subramanian, A., Wiese, A.: A PTAS for the horizontal rectangle stabbing problem. In: IPCO, pp. 361\u2013374 (2022)","DOI":"10.1007\/978-3-031-06901-7_27"},{"issue":"3","key":"2106_CR34","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":"2106_CR35","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B.: Approximating maximum independent set for rectangles in the plane. In: FOCS, pp. 339\u2013350 (2021)","DOI":"10.1109\/FOCS52979.2021.00042"},{"key":"2106_CR36","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Wiese, A.: A $$(2+\\epsilon )$$-approximation algorithm for the storage allocation problem. In: ICALP, pp. 973\u2013984 (2015)","DOI":"10.1007\/978-3-662-47672-7_79"},{"key":"2106_CR37","unstructured":"M\u00f6mke, T., Wiese, A.: Breaking the barrier of 2 for the storage allocation problem. In: ICALP, pp. 86:1\u201386:19 (2020)"},{"issue":"6","key":"2106_CR38","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":"2106_CR39","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: Weighted geometric set cover via quasi-uniform sampling. In: STOC, pp. 641\u2013648 (2010)","DOI":"10.1145\/1806689.1806777"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02106-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02106-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02106-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T20:06:11Z","timestamp":1732219571000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02106-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2106"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02106-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,6,13]]},"assertion":[{"value":"12 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}