{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:31:38Z","timestamp":1777501898896,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61662088"],"award-info":[{"award-number":["61662088"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s11590-021-01724-1","type":"journal-article","created":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T14:03:27Z","timestamp":1616249007000},"page":"2165-2180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Approximation algorithms for the multiprocessor scheduling with submodular penalties"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1650-2625","authenticated-orcid":false,"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"issue":"1","key":"1724_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55\u201366 (1998)","journal-title":"J. Sched."},{"key":"1724_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp: 671\u2013680. ACM (2014)","DOI":"10.1145\/2623330.2623637"},{"issue":"1","key":"1724_CR3","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.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13(1), 64\u201378 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"1724_CR4","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.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63(1\u20132), 191\u2013200 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"1724_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L Fleischer","year":"2003","unstructured":"Fleischer, L., Iwata, S.: A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl. Math. 131(2), 311\u2013322 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1724_CR6","volume-title":"Submodular Functions And Optimization","author":"S Fujishige","year":"2008","unstructured":"Fujishige, S.: Submodular Functions And Optimization, vol. 47. Elsevier, Amsterdam (2008)"},{"issue":"9","key":"1724_CR7","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"1724_CR8","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"1724_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-020-01632-w","author":"L Guan","year":"2020","unstructured":"Guan, L., Li, W., Xiao, M.: Online algorithms for the mixed ring loading problem with two nodes. Optim. Lett. (2020). https:\/\/doi.org\/10.1007\/s11590-020-01632-w","journal-title":"Optim. Lett."},{"issue":"1","key":"1724_CR10","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM (JACM) 34(1), 144\u2013162 (1987)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1724_CR11","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2), 457\u2013485 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1724_CR12","unstructured":"Jansen K., Klein K.M., Verschae J. Closing the gap for makespan scheduling via sparsification techniques (2016). arXiv preprint arXiv:1604.07153"},{"issue":"7","key":"1724_CR13","doi-asserted-by":"publisher","first-page":"3025","DOI":"10.1007\/s00453-019-00566-9","volume":"81","author":"I Kones","year":"2019","unstructured":"Kones, I., Levin, A.: A unified framework for designing EPTAS for load balancing on parallel machines. Algorithmica 81(7), 3025\u20133046 (2019)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"1724_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1\u20133), 259\u2013271 (1990)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1724_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ipl.2013.08.004","volume":"114","author":"W Li","year":"2014","unstructured":"Li, W., Li, J., Guan, L.: Approximation algorithms for the ring loading problem with penalty cost. Inf. Process. Lett. 114(1\u20132), 56\u201359 (2014)","journal-title":"Inf. Process. Lett."},{"key":"1724_CR16","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2015.10.007","volume":"607","author":"W Li","year":"2015","unstructured":"Li, W., Li, J., Zhang, X., Chen, Z.: Penalty cost constrained identical parallel machine scheduling problem. Theor. Comput. Sci. 607, 181\u2013192 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1724_CR17","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.: Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica 73(2), 460\u2013482 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"1724_CR18","first-page":"1","volume":"2020","author":"X Liu","year":"2020","unstructured":"Liu, X., Li, W.: Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties. J. Comb. Optim. 2020(4), 1\u201313 (2020)","journal-title":"J. Comb. Optim."},{"key":"1724_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.3390\/math8010133","volume":"8","author":"X Liu","year":"2020","unstructured":"Liu, X., Li, W.: Approximation algorithm for the single machine scheduling problem with release dates and submodular rejection penalty. Mathematics 8, 133 (2020)","journal-title":"Mathematics"},{"key":"1724_CR20","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.3390\/math8101785","volume":"8","author":"X Liu","year":"2020","unstructured":"Liu, X., Xing, P., Li, W.: Approximation algorithms for the submodular load balancing with submodular penalties. Mathematics 8, 1785 (2020)","journal-title":"Mathematics"},{"key":"1724_CR21","volume-title":"Mathematical Programming The State of the Art, PP: 235\u2013257","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Gr\u00f6tschel, M., Korte, B. (eds.) Mathematical Programming The State of the Art, PP: 235\u2013257. Springer, Berlin (1983)"},{"key":"1724_CR22","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman B., Jegelka, S., Krause, A. Streaming non-monotone submodular maximization: personalized video summarization on the fly. In: The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18) , pp. 1379\u20131386. AAAI (2018)","DOI":"10.1609\/aaai.v32i1.11529"},{"issue":"3","key":"1724_CR23","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1016\/j.ejor.2014.09.028","volume":"241","author":"J Ou","year":"2015","unstructured":"Ou, J., Zhong, X., Wang, G.: An improved heuristic for parallel machine scheduling with rejection. Eur. J. Oper. Res. 241(3), 653\u2013661 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"1724_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(85)90009-5","volume":"10","author":"CN Potts","year":"1985","unstructured":"Potts, C.N.: Analysis of a linear programming heuristic of scheduling unrelated parallel-machines. Discrete Appl. Math. 10, 155\u2013164 (1985)","journal-title":"Discrete Appl. Math."},{"key":"1724_CR25","unstructured":"Sharma Y., Swamy C., Williamson D.P. Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1275\u20131284. SIAM (2007)"},{"key":"1724_CR26","unstructured":"Wei K., Iyer R.K., Wang S., Bai W., Bilmes J.A. Mixed robust\/average submodular partitioning: Fast algorithms, guarantees, and applications. In: Proceedings of Advances in Neural Information Processing Systems, pp. 2233\u20132241. MIT (2015)"},{"issue":"1","key":"1724_CR27","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/s10878-016-0044-6","volume":"35","author":"X Zhang","year":"2018","unstructured":"Zhang, X., Xu, D., Du, D., Wu, C.: Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J. Comb. Optim. 35(1), 318\u2013330 (2018)","journal-title":"J. Comb. Optim."},{"key":"1724_CR28","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10288-016-0339-6","volume":"15","author":"X Zhong","year":"2017","unstructured":"Zhong, X., Ou, J.: Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. Q. J. Oper. Res. (4OR) 15, 387\u2013406 (2017)","journal-title":"Q. J. Oper. Res. (4OR)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01724-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01724-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01724-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T01:54:37Z","timestamp":1671674077000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01724-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,20]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["1724"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01724-1","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,20]]},"assertion":[{"value":"3 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2021","order":3,"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 they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}