{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T07:15:38Z","timestamp":1750835738895,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030794156"},{"type":"electronic","value":"9783030794163"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_8","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"131-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Schemes for Multiperiod Binary Knapsack Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0872-4532","authenticated-orcid":false,"given":"Zuguang","family":"Gao","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7446-0953","authenticated-orcid":false,"given":"John R.","family":"Birge","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7373-1734","authenticated-orcid":false,"given":"Varun","family":"Gupta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/S0377-2217(99)00265-9","volume":"123","author":"R Andonov","year":"2000","unstructured":"Andonov, R., Poirriez, V., Rajopadhye, S.: Unbounded knapsack problem: dynamic programming revisited. Eur. J. Oper. Res. 123(2), 394\u2013407 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"8_CR2","unstructured":"Aouad, A., Segev, D.: An approximate dynamic programming approach to the incremental knapsack problem. arXiv preprint arXiv:2010.07633 (2020)"},{"key":"8_CR3","unstructured":"Bienstock, D., Sethuraman, J., Ye, C.: Approximation algorithms for the incremental knapsack problem via disjunctive programming. arXiv preprint arXiv:1311.4563 (2013)"},{"key":"8_CR4","unstructured":"Chan, T.M.: Approximation Schemes for 0-1 Knapsack. In: Seidel, R. (ed.) 1st Symposium on Simplicity in Algorithms (SOSA 2018). OpenAccess Series in Informatics (OASIcs), vol. 61, pp. 5:1\u20135:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"issue":"3","key":"8_CR5","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":"8_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.dam.2019.02.016","volume":"264","author":"F Della Croce","year":"2019","unstructured":"Della Croce, F., Pferschy, U., Scatamacchia, R.: On approximating the incremental knapsack problem. Discrete Appl. Math. 264, 26\u201342 (2019)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"8_CR7","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."},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-319-96151-4_14","volume-title":"Combinatorial Optimization","author":"Y Faenza","year":"2018","unstructured":"Faenza, Y., Malinovic, I.: A PTAS for the time-invariant incremental knapsack problem. In: Lee, J., Rinaldi, G., Mahjoub, A.R. (eds.) ISCO 2018. LNCS, vol. 10856, pp. 157\u2013169. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96151-4_14"},{"key":"8_CR9","unstructured":"Faenza, Y., Segev, D., Zhang, L.: Approximation algorithms for the generalized incremental knapsack problem. arXiv preprint arXiv:2009.07248 (2020)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Gao, Z., Birge, J.R., Gupta, V.: Approximation schemes for multiperiod binary knapsack problems. arXiv preprint arXiv:2104.00034 (2021)","DOI":"10.1007\/978-3-030-79416-3_8"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/11764298_4","volume-title":"Experimental Algorithms","author":"J Hartline","year":"2006","unstructured":"Hartline, J., Sharp, A.: An incremental model for combinatorial maximization problems. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 36\u201348. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11764298_4"},{"issue":"4","key":"8_CR12","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 (JACM) 22(4), 463\u2013468 (1975)","journal-title":"J. ACM (JACM)"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-27660-6_26","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K Jansen","year":"2012","unstructured":"Jansen, K.: A fast approximation scheme for the multiple knapsack problem. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 313\u2013324. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27660-6_26"},{"key":"8_CR14","unstructured":"Jin, C.: An improved FPTAS for 0\u20131 Knapsack. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 76:1\u201376:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019)"},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U.: Improved dynamic programming in connection with an FPTAs for the knapsack problem. J. Comb. Optim. 8(1), 5\u201311 (2004)","journal-title":"J. Comb. Optim."},{"key":"8_CR16","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":"8_CR17","unstructured":"Lau, H.C., Lim, M.K.: Multi-period multi-dimensional knapsack problem and its application to available-to-promise (2004)"},{"issue":"4","key":"8_CR18","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":"2","key":"8_CR19","first-page":"289","volume":"31","author":"EY Lin","year":"2010","unstructured":"Lin, E.Y., Chen, M.: A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive apl2 code. J. Inf. Optim. Sci. 31(2), 289\u2013303 (2010)","journal-title":"J. Inf. Optim. Sci."},{"issue":"2","key":"8_CR20","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1057\/palgrave.jors.2601661","volume":"55","author":"EY Lin","year":"2004","unstructured":"Lin, E.Y., Wu, C.M.: The multiple-choice multi-period knapsack problem. J. Oper. Res. Soc. 55(2), 187\u2013197 (2004)","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1112\/plms\/s1-28.1.486","volume":"1","author":"GB Mathews","year":"1896","unstructured":"Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. 1(1), 486\u2013490 (1896)","journal-title":"Proc. Lond. Math. Soc."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.endm.2010.05.052","volume":"36","author":"E Moreno","year":"2010","unstructured":"Moreno, E., Espinoza, D., Goycoolea, M.: Large-scale multi-period precedence constrained knapsack problem: a mining application. Electron. Notes Discrete Math. 36, 407\u2013414 (2010)","journal-title":"Electron. Notes Discrete Math."},{"key":"8_CR23","unstructured":"Randeniya, R.: Multiple-choice Multi-period Knapsack Problem (MCMKP): Application and Solution Approach"},{"key":"8_CR24","unstructured":"Rhee, D.: Faster fully polynomial approximation schemes for knapsack problems. Ph.D. thesis, Massachusetts Institute of Technology (2015)"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.ijpe.2017.06.025","volume":"193","author":"M Samavati","year":"2017","unstructured":"Samavati, M., Essam, D., Nehring, M., Sarker, R.: A methodology for the large-scale multi-period precedence-constrained knapsack problem: an application in the mining industry. Int. J. Prod. Econ. 193, 12\u201320 (2017)","journal-title":"Int. J. Prod. Econ."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:21:35Z","timestamp":1623972095000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}