{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:12:47Z","timestamp":1757617967468,"version":"3.44.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10878-025-01314-2","type":"journal-article","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T16:31:34Z","timestamp":1747845094000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties"],"prefix":"10.1007","volume":"49","author":[{"given":"Tianjiao","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gengsheng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,21]]},"reference":[{"issue":"1","key":"1314_CR1","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y Bartal","year":"2000","unstructured":"Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J. Discret. Math. 13(1):64\u201378","journal-title":"SIAM J. Discret. Math."},{"issue":"1\u20132","key":"1314_CR2","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du D, Lu R, Xu D (2012) A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63(1\u20132):191\u2013200","journal-title":"Algorithmica"},{"key":"1314_CR3","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":"1314_CR4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5:287\u2013326","journal-title":"Ann. Discret. Math."},{"issue":"1","key":"1314_CR5","first-page":"207","volume":"11","author":"J Guo","year":"2023","unstructured":"Guo J, Liu W, Hou B (2023) An approximation algorithm for $$P$$-prize-collecting set cover problem. J. Oper. Res. Soc. China. 11(1):207\u2013217","journal-title":"J. Oper. Res. Soc. China."},{"key":"1314_CR6","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":"1314_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s10878-024-01212-z","volume":"4","author":"B Hou","year":"2024","unstructured":"Hou B, Guo T, Gao S, Wang G, Wu W, Liu W (2024) $$W$$-prize-collecting scheduling problem on parallel machines. J. Comb. Optim. 4:26","journal-title":"J. Comb. Optim."},{"key":"1314_CR8","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2020.07.014","volume":"844","author":"X Hou","year":"2020","unstructured":"Hou X, Liu W, Hou B (2020) An approximation algorithm for the $$k$$-prize-collecting multicut on a tree problem. Theor. Comput. Sci. 844:26\u201333","journal-title":"Theor. Comput. Sci."},{"key":"1314_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.3390\/math8010133","volume":"8","author":"X Liu","year":"2020","unstructured":"Liu X, Li W (2020) Approximation algorithm for the single machine scheduling problem with release dates and submodular rejection penalty. Mathematics 8:133","journal-title":"Mathematics"},{"issue":"3","key":"1314_CR10","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1007\/s10878-020-00568-2","volume":"44","author":"X Liu","year":"2020","unstructured":"Liu X, Li W (2020) Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties. J. Comb. Optim. 44(3):1964\u20131976","journal-title":"J. Comb. Optim."},{"key":"1314_CR11","doi-asserted-by":"publisher","first-page":"2373","DOI":"10.1007\/s11590-021-01831-z","volume":"16","author":"X Liu","year":"2022","unstructured":"Liu X, Li W, Xie R (2022) A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum power cover problem. Optim. Lett. 16:2373\u20132385","journal-title":"Optim. Lett."},{"issue":"3","key":"1314_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-022-1665-9","volume":"17","author":"X Liu","year":"2023","unstructured":"Liu X, Li W, Yang J (2023) A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum vertex cover problem with submodular penalties. Front. Comput. Sci. 17(3):173404","journal-title":"Front. Comput. Sci."},{"key":"1314_CR13","first-page":"235","volume-title":"Mathematical Programing 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 Programing the State of the Art. Springer, Berlin, Heidelberg, pp 235\u2013237"},{"key":"1314_CR14","doi-asserted-by":"crossref","unstructured":"Sun R, Deng B (2022) $$W$$-prize-collecting scheduling problem on a single machine. In: Proceedings of the 2022 6th International Conference on Computer Science and Artificial Intelligence, pp. 237\u2013242","DOI":"10.1145\/3577530.3577568"},{"key":"1314_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.3390\/math10010061","volume":"10","author":"W Wang","year":"2022","unstructured":"Wang W, Liu X (2022) Combinatorial 2-Approximation algorithm for the parallel-machine scheduling with release times and submodular penalties. Mathematics 10:61","journal-title":"Mathematics"},{"key":"1314_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10878-021-00842-x","volume":"44","author":"H Zheng","year":"2022","unstructured":"Zheng H, Gao S, Liu W, Wu W, Du D, Hou B (2022) Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties. J. Comb. Optim. 44:343\u2013353","journal-title":"J. Comb. Optim."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01314-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01314-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01314-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:13:11Z","timestamp":1757171591000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01314-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,21]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1314"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01314-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,5,21]]},"assertion":[{"value":"30 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interests regarding the publication of this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"72"}}