{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T15:17:41Z","timestamp":1770995861316,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T00:00:00Z","timestamp":1650672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T00:00:00Z","timestamp":1650672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The minimum hitting set of bundles problem (<jats:sc>Mhsb<\/jats:sc>) is a natural generalization of the minimum hitting set problem, where instead of hitting single elements, bundles of elements are hit. More specifically, we are given a ground set of elements and a family of sets. Every set in this family contains bundles of elements, which are subsets of the ground set. The task is to find a collection of elements of minimum size such that at least one bundle of every set in the family is hit. Motivated by several applications, we consider <jats:sc>Mhsb<\/jats:sc>\u00a0restricted to interval and 2-dimensional interval bundles. We study the computational complexity and give polynomial-time algorithms for several classes of instances with these special structured bundles.<\/jats:p>","DOI":"10.1007\/s00453-022-00964-6","type":"journal-article","created":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T11:02:36Z","timestamp":1650711756000},"page":"2222-2239","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimum Hitting Set of Interval Bundles Problem: Computational Complexity and Approximability"],"prefix":"10.1007","volume":"84","author":[{"given":"Marinus","family":"Gottschau","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1677-4786","authenticated-orcid":false,"given":"Marilena","family":"Leichter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,23]]},"reference":[{"issue":"45","key":"964_CR1","doi-asserted-by":"publisher","first-page":"4534","DOI":"10.1016\/j.tcs.2009.08.017","volume":"410","author":"E Angel","year":"2009","unstructured":"Angel, E., Bampis, E., Gourv\u00e8s, L.: On the minimum hitting set of bundles problem. Theor. Comput. Sci. 410(45), 4534\u20134542 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"964_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: Automata. Languages and Programming, pp. 250\u2013261. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14165-2_22"},{"issue":"3","key":"964_CR3","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","volume":"24","author":"D Bertsimas","year":"1999","unstructured":"Bertsimas, D., Teo, C., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105\u2013114 (1999)","journal-title":"Oper. Res. Lett."},{"key":"964_CR4","doi-asserted-by":"crossref","unstructured":"Chang, J., Gabow, H.N., Khuller, S.: A model for minimizing active processor time. In: European Symposium on Algorithms, pp. 289\u2013300. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33090-2_26"},{"issue":"6","key":"964_CR5","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/s10951-017-0531-3","volume":"20","author":"J Chang","year":"2017","unstructured":"Chang, J., Khuller, S., Mukherjee, K.: Lp rounding and combinatorial algorithms for minimizing active and busy time. J. Sched. 20(6), 657\u2013680 (2017)","journal-title":"J. Sched."},{"key":"964_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 72\u201383. Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_7"},{"issue":"4","key":"964_CR7","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1007\/s10878-013-9629-5","volume":"29","author":"P Damaschke","year":"2015","unstructured":"Damaschke, P.: Parameterizations of hitting set of bundles and inverse scope. J. Comb. Optim. 29(4), 847\u2013858 (2015)","journal-title":"J. Comb. Optim."},{"key":"964_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 624\u2013633. ACM, New York (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"964_CR9","unstructured":"Eskandarzadeh, S., Kalinowski, T., Waterer, H.: Maintenance scheduling in a railway corricdor. arXiv preprint arXiv:1910.10348 (2019)"},{"key":"964_CR10","doi-asserted-by":"crossref","unstructured":"Fang, X., Gao, H., Li, J., Li, Y.: Application-aware data collection in wireless sensor networks. In: 2013 Proceedings IEEE INFOCOM, pp. 1645\u20131653 (2013)","DOI":"10.1109\/INFCOM.2013.6566961"},{"key":"964_CR11","doi-asserted-by":"crossref","unstructured":"Fong, K.C.K., Li, M., Li, Y., Poon, S.H., Wu, W., Zhao, Y.: Scheduling tasks to minimize active time on a processor with unlimited capacity. In: Theory and Applications of Models of Computation, pp. 247\u2013259. Springer (2017)","DOI":"10.1007\/978-3-319-55911-7_18"},{"issue":"3","key":"964_CR12","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"key":"964_CR13","doi-asserted-by":"crossref","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 671\u2013680 (2009)","DOI":"10.1109\/FOCS.2009.31"},{"key":"964_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"964_CR15","unstructured":"Khandekar, R., Schieber, B., Shachnai, H., Tamir, T.: Minimizing busy time in multiple machine real-time scheduling. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2010)"},{"key":"964_CR16","doi-asserted-by":"crossref","unstructured":"Koehler, F., Khuller, S.: Busy time scheduling on a bounded number of machines. In: Workshop on Algorithms and Data Structures, pp. 521\u2013532. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_44"},{"key":"964_CR17","volume-title":"Combinatorial Optimization","author":"BH Korte","year":"2011","unstructured":"Korte, B.H., Vygen, J., Korte, B., Vygen, J.: Combinatorial Optimization, vol. 1. Springer, Berlin (2011)"},{"issue":"1","key":"964_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/42201.42203","volume":"13","author":"TK Sellis","year":"1988","unstructured":"Sellis, T.K.: Multiple-query optimization. ACM Trans. Database Syst. 13(1), 23\u201352 (1988)","journal-title":"ACM Trans. Database Syst."},{"key":"964_CR19","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2013)"},{"issue":"2","key":"964_CR20","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s10589-009-9269-y","volume":"45","author":"PJ Wan","year":"2010","unstructured":"Wan, P.J., Du, D.Z., Pardalos, P., Wu, W.: Greedy approximations for minimum submodular cover with submodular cost. Comput. Optim. Appl. 45(2), 463\u2013474 (2010)","journal-title":"Comput. Optim. Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00964-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00964-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00964-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:11:33Z","timestamp":1658409093000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00964-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,23]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["964"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00964-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,23]]},"assertion":[{"value":"3 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}