{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:49:18Z","timestamp":1777502958481,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/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"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11761078"],"award-info":[{"award-number":["11761078"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11861075"],"award-info":[{"award-number":["11861075"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10878-019-00406-0","type":"journal-article","created":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T16:03:35Z","timestamp":1553616215000},"page":"689-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Improved approximation algorithms for the combination problem of parallel machine scheduling and path"],"prefix":"10.1007","volume":"38","author":[{"given":"Li","family":"Guan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianping","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3094-4347","authenticated-orcid":false,"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junran","family":"Lichen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"406_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 GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J Sched 1:55\u201366","journal-title":"J Sched"},{"key":"406_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.03.005","volume":"96","author":"L Chen","year":"2018","unstructured":"Chen L, Jansen K, Zhang G (2018) On the optimality of exact and approximation algorithms for scheduling problems. J Comput Syst Sci 96:1\u201332","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"406_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E Dijkstra","year":"1959","unstructured":"Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"5","key":"406_CR4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0020-0190(02)00205-3","volume":"83","author":"F Ergun","year":"2002","unstructured":"Ergun F, Sinha R, Zhang L (2002) An improved FPTAS for restricted shortest path. Inf Process Lett 83(5):287\u2013291","journal-title":"Inf Process Lett"},{"key":"406_CR5","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"1","author":"R Graham","year":"1966","unstructured":"Graham R (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 1:1563\u20131581","journal-title":"Bell Syst Tech J"},{"issue":"1","key":"406_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problems. Math Oper Res 17(1):36\u201342","journal-title":"Math Oper Res"},{"issue":"1","key":"406_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J ACM 34(1):144\u2013162","journal-title":"J ACM"},{"issue":"2","key":"406_CR8","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen K (2010) 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","journal-title":"SIAM J Discrete Math"},{"key":"406_CR9","unstructured":"Jansen K, Klein KM, Verschae J (2016) Closing the gap for makespan scheduling via sparsification techniques. In: Proceedings of the 43rd international colloquium on automata, languages, and programming, pp 72:1\u201372:13"},{"issue":"1","key":"406_CR10","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/s10878-013-9670-4","volume":"29","author":"K Nip","year":"2015","unstructured":"Nip K, Wang Z, Nobibon FT, Leus R (2015) A combination of flow shop scheduling and the shortest path problem. J Comb Optim 29(1):36\u201352","journal-title":"J Comb Optim"},{"key":"406_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.tcs.2015.12.027","volume":"654","author":"K Nip","year":"2016","unstructured":"Nip K, Wang Z, Xing W (2016) A study on several combination problems of classic shop scheduling and shortest path. Theor Comput Sci 654:175\u2013187","journal-title":"Theor Comput Sci"},{"key":"406_CR12","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.tcs.2012.06.003","volume":"460","author":"Z Wang","year":"2012","unstructured":"Wang Z, Cui Z (2012) Combination of parallel machine scheduling and vertex cover. Theor Comput Sci 460:10\u201315","journal-title":"Theor Comput Sci"},{"issue":"3","key":"406_CR13","first-page":"577","volume":"10","author":"Z Wang","year":"2014","unstructured":"Wang Z, Hong W, He D (2014) A combination of parallel machine scheduling and the covering problem. Pac J Optim 10(3):577\u2013591","journal-title":"Pac J Optim"},{"key":"406_CR14","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1287\/opre.35.1.70","volume":"35","author":"A Warburton","year":"1987","unstructured":"Warburton A (1987) Approximation of Pareto optima in multiple-objective shortest path problems. Oper Res 35:70\u201379","journal-title":"Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00406-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00406-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00406-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T00:25:29Z","timestamp":1585095929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00406-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["406"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00406-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"26 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}