{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:02Z","timestamp":1740122402499,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T00:00:00Z","timestamp":1600992000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T00:00:00Z","timestamp":1600992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003787","name":"Natural Science Foundation of Hebei Province","doi-asserted-by":"publisher","award":["A2019205092","A2019205089"],"award-info":[{"award-number":["A2019205092","A2019205089"]}],"id":[{"id":"10.13039\/501100003787","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["11971146"],"award-info":[{"award-number":["11971146"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hebei Province Foundation for Returnees","award":["CL201714"],"award-info":[{"award-number":["CL201714"]}]},{"name":"Overseas Expertise Introduction Program of Hebei Auspices","award":["25305008"],"award-info":[{"award-number":["25305008"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s10878-020-00653-6","type":"journal-article","created":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T13:04:28Z","timestamp":1601039068000},"page":"1065-1074","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An approximation algorithm for submodular hitting set problem with linear penalties"],"prefix":"10.1007","volume":"40","author":[{"given":"Shaojing","family":"Du","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suogang","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6872-3315","authenticated-orcid":false,"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,25]]},"reference":[{"key":"653_CR1","unstructured":"Bringmann K, Kozma L, Moran S, Narayanaswamy NS (2016) Hitting set for hypergraphs of low VC-dimension. In: LIPIcs-Leibniz international proceedings in informatics. 24th annual European symposium on algorithms. ESA 2016. Schloss Dagstuhl-Leibniz-Zentrum f$$\\ddot{u}$$r Informatik. Dagstuhl Publishing, Germany, pp 1\u201318"},{"key":"653_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2017.12.018","volume":"240","author":"N Bus","year":"2018","unstructured":"Bus N, Mustafa N, Ray S (2018) Practical and efficient algorithms for the geometric hitting set problem. J Discrete Appl Math 240:25\u201332","journal-title":"J Discrete Appl Math"},{"key":"653_CR3","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.future.2016.02.009","volume":"67","author":"D Carastan-Santos","year":"2017","unstructured":"Carastan-Santos D, Camargo R, Martin D, Song S, Rozante L (2017) Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters. Future Gener Comput Syst 67:418\u2013429","journal-title":"Future Gener Comput Syst"},{"key":"653_CR4","volume-title":"Design and analysis of approximation algorithms","author":"D Du","year":"2011","unstructured":"Du D, Ko K, Hu X (2011) Design and analysis of approximation algorithms. Springer, New York"},{"key":"653_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T Eiter","year":"1995","unstructured":"Eiter T, Gottlob G (1995) Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput 24:1\u20132","journal-title":"SIAM J Comput"},{"key":"653_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2018.09.027","volume":"767","author":"K Elbassioni","year":"2019","unstructured":"Elbassioni K, Rauf I, Ray S (2019) A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs. Theor Comput Sci 767:26\u201333","journal-title":"Theor Comput Sci"},{"key":"653_CR7","volume-title":"Submodular functions and optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige S (2005) Submodular functions and optimization, 2nd edn. Elsevier, Amsterdam","edition":"2"},{"key":"653_CR8","series-title":"FoIKS 2004. Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24627-5_1","volume-title":"Foundations of information and knowledge systems","author":"G Gottlob","year":"2004","unstructured":"Gottlob G (2004) Hypergraph transversals. In: Seipel D, Turull-Torres JM (eds) Foundations of information and knowledge systems, vol 2942. FoIKS 2004. Lecture notes in computer science. Springer, Berlin, pp 1\u20135"},{"issue":"5","key":"653_CR9","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2001","unstructured":"Halperin E (2001) Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J Comput 31(5):1608\u20131623","journal-title":"SIAM J Comput"},{"key":"653_CR10","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s11590-017-1135-8","volume":"13","author":"L Han","year":"2017","unstructured":"Han L, Xu D, Du D, Wu C (2017) A 5-approximation algorithm for the $$k$$-prize-collecting Steiner tree problem. Optim Lett 13:573\u2013585","journal-title":"Optim Lett"},{"key":"653_CR11","doi-asserted-by":"crossref","unstructured":"Iwata S, Nagano K (2009) Submodular function minimization under covering constraints. In: Proceedings of the 50th annual symposium on foundations of computer science, pp 671\u2013680","DOI":"10.1109\/FOCS.2009.31"},{"issue":"1","key":"653_CR12","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1006\/jagm.1997.0872","volume":"25","author":"M Krivelevich","year":"1997","unstructured":"Krivelevich M (1997) Approximate set covering in uniform hypergraphs. J Algorithms 25(1):118\u2013143","journal-title":"J Algorithms"},{"key":"653_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2012.11.037","volume":"476","author":"Y Li","year":"2013","unstructured":"Li Y, Du D, Xiu N, Xu D (2013) A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties. Theor Comput Sci 476:109\u2013117","journal-title":"Theor Comput Sci"},{"issue":"3","key":"653_CR14","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s10878-012-9540-5","volume":"27","author":"Y Li","year":"2014","unstructured":"Li Y, Du D, Xiu N, Xu D (2014) A unified dual-fitting approximation algorithm for the facility location problems with linear\/submodular penalties. J Combin Optim 27(3):609\u2013620","journal-title":"J Combin Optim"},{"issue":"2","key":"653_CR15","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"Li Y, Du D, Xiu N, Xu D (2015) Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica 73(2):460\u2013482","journal-title":"Algorithmica"},{"key":"653_CR16","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-030-27195-4_19","volume-title":"Algorithmic aspects in information and management","author":"X Liu","year":"2019","unstructured":"Liu X, Li W (2019) A primal dual approximation algorithm for the multicut problem in trees with submodular penalties. In: Du D, Li L, Sun X, Zhang J (eds) Algorithmic aspects in information and management, vol 11640. Lecture notes in computer science. Springer, Cham, pp 203\u2013211"},{"key":"653_CR17","first-page":"235","volume-title":"Mathematical program in the state of the art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz L (1983) Submodular functions and convexity. In: Bachm A, Grtschel M, Korte B (eds) Mathematical program in the state of the art. Springer, Berlin, pp 235\u2013237"},{"key":"653_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2018.09.002","volume":"141","author":"R Madireddy","year":"2019","unstructured":"Madireddy R, Mudgal A (2019) NP-hardness of geometric set cover and hitting set with rectangles containing a common point. Inf Process Lett 141:1\u20138","journal-title":"Inf Process Lett"},{"key":"653_CR19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.disopt.2004.11.002","volume":"2","author":"M Okun","year":"2005","unstructured":"Okun M (2005) On approximation of the vertex cover problem in hypergraphs. Discrete Optim 2:101\u2013111","journal-title":"Discrete Optim"},{"key":"653_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2014.03.029","volume":"555","author":"M Ouali","year":"2014","unstructured":"Ouali M, Fohlin H, Srivastav A (2014) A randomised approximation algorithm for the hitting set problem. Theor Comput Sci 555:23\u201334","journal-title":"Theor Comput Sci"},{"key":"653_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-05093-2","volume-title":"Matrices and mathematical programming: an introduction for economics","author":"N Rau","year":"1981","unstructured":"Rau N (1981) Matrices and mathematical programming: an introduction for economics. Macmillan, London"},{"issue":"2","key":"653_CR22","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s10589-009-9269-y","volume":"45","author":"P Wan","year":"2010","unstructured":"Wan P, Du D, Pardalos P, Wu W (2010) Greedy approximations for minimum submodular cover with submodular cost. Comput Optim Appl 45(2):463\u2013474","journal-title":"Comput Optim Appl"},{"issue":"3","key":"653_CR23","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s101070100262","volume":"91","author":"D Williamson","year":"2002","unstructured":"Williamson D (2002) The primal-dual method for approximation algorithms. Math Program 91(3):451\u2013453","journal-title":"Math Program"},{"key":"653_CR24","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2016.04.005","volume":"630","author":"D Xu","year":"2016","unstructured":"Xu D, Wang F, Du D, Wu C (2016) Approximation algorithms for submodular vertex cover problems with linear\/submodular penalties using primal-dual technique. Theor Comput Sci 630:117\u2013125","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00653-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00653-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00653-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,25]],"date-time":"2021-09-25T01:56:53Z","timestamp":1632535013000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00653-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,25]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["653"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00653-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,9,25]]},"assertion":[{"value":"18 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}