{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:22:05Z","timestamp":1742980925979,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319947754"},{"type":"electronic","value":"9783319947761"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94776-1_6","type":"book-chapter","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T01:48:06Z","timestamp":1530236886000},"page":"63-75","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for a Two-Phase Knapsack Problem"],"prefix":"10.1007","author":[{"given":"Kameng","family":"Nip","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenbo","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7"},{"key":"6_CR2","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.: Combination of parallel machine scheduling and vertex cover. Theoret. Comput. Sci. 460, 10\u201315 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1007\/978-3-642-38768-5_60","volume-title":"Computing and Combinatorics","author":"K Nip","year":"2013","unstructured":"Nip, K., Wang, Z.: Combination of two-machine flow shop scheduling and shortest path problems. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 680\u2013687. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38768-5_60"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-319-21398-9_8","volume-title":"Computing and Combinatorics","author":"K Nip","year":"2015","unstructured":"Nip, K., Wang, Z., Xing, W.: Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 97\u2013108. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21398-9_8"},{"issue":"1","key":"6_CR5","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., Talla Nobibon, F., Leus, R.: A combination of flow shop scheduling and the shortest path problem. J. Comb. Optim. 29(1), 36\u201352 (2015)","journal-title":"J. Comb. Optim."},{"key":"6_CR6","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.: A study on several combination problems of classic shop scheduling and shortest path. Theoret. Comput. Sci. 654, 175\u2013187 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713\u2013728 (2005)","journal-title":"SIAM J. Comput."},{"key":"6_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)"},{"issue":"4","key":"6_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"EL Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1137\/080731207","volume":"39","author":"K Jansen","year":"2010","unstructured":"Jansen, K.: Parameterized approximation scheme for the multiple knapsack problem. SIAM J. Comput. 39(4), 1392\u20131412 (2010)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Program. 62(3), 461\u2013474 (1993)","journal-title":"Math. Program."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: improving the factor of $$1 - 1\/e$$. In: FOCS 2006, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"issue":"3","key":"6_CR15","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1287\/moor.1110.0499","volume":"36","author":"L Fleischer","year":"2011","unstructured":"Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3), 416\u2013431 (2011)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"6_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0377-2217(87)90165-2","volume":"28","author":"K Dudzi\u0144ski","year":"1987","unstructured":"Dudzi\u0144ski, K., Walukiewicz, S.: Exact methods for the knapsack problem and its generalizations. Eur. J. Oper. Res. 28(1), 3\u201321 (1987)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"6_CR17","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0377-2217(93)E0211-F","volume":"81","author":"RE Johnston","year":"1995","unstructured":"Johnston, R.E., Khan, L.R.: Bounds for nested knapsack problems. Eur. J. Oper. Res. 81(1), 154\u2013165 (1995)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"6_CR18","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2005.10.036","volume":"352","author":"E Xavier","year":"2006","unstructured":"Xavier, E., Miyazawa, F.: Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci. 352(1), 71\u201384 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1287\/opre.29.3.612","volume":"29","author":"BH Faaland","year":"1981","unstructured":"Faaland, B.H.: The multiperiod knapsack problem. Oper. Res. 29(3), 612\u2013616 (1981)","journal-title":"Oper. Res."},{"issue":"16","key":"6_CR20","doi-asserted-by":"publisher","first-page":"1827","DOI":"10.1016\/j.dam.2010.04.006","volume":"159","author":"S Kosuch","year":"2011","unstructured":"Kosuch, S., Lisser, A.: On two-stage stochastic knapsack problems. Discrete Appl. Math. 159(16), 1827\u20131841 (2011)","journal-title":"Discrete Appl. Math."},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/j.dam.2013.02.015","volume":"165","author":"S Kosuch","year":"2014","unstructured":"Kosuch, S.: Approximability of the two-stage stochastic knapsack problem with discretely distributed weights. Discrete Appl. Math. 165, 192\u2013204 (2014)","journal-title":"Discrete Appl. Math."},{"key":"6_CR22","first-page":"93","volume":"8","author":"S Dempe","year":"2000","unstructured":"Dempe, S., Richter, K.: Bilevel programming with knapsack constraint. CEJOR 8, 93\u2013107 (2000)","journal-title":"CEJOR"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.08.008","volume":"497","author":"L Chen","year":"2013","unstructured":"Chen, L., Zhang, G.: Approximation algorithms for a bi-level knapsack problem. Theoret. Comput. Sci. 497, 1\u201312 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"6_CR24","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2), 823\u2013838 (2014)","journal-title":"SIAM J. Optim."},{"key":"6_CR25","unstructured":"Chen, L., Zhang, G.: Packing groups of items into multiple knapsacks. In: Ollinger, N., Vollmer, H. (eds.) STACS 2016. LIPIcs, vol. 47, pp. 28:1\u201328:13 (2016)"},{"issue":"1","key":"6_CR26","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1137\/0216012","volume":"16","author":"FD Murgolo","year":"1987","unstructured":"Murgolo, F.D.: An efficient approximation scheme for variable-sized bin packing. SIAM J. Comput. 16(1), 149\u2013161 (1987)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"6_CR27","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + $$\\epsilon $$ in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94776-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:33:14Z","timestamp":1710347594000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94776-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319947754","9783319947761"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94776-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Qing Dao","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 July 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2018.sdu.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}