{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T10:05:32Z","timestamp":1775297132773,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T00:00:00Z","timestamp":1544054400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10479-018-3111-9","type":"journal-article","created":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T03:54:12Z","timestamp":1544068452000},"page":"367-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximation schemes for r-weighted Minimization Knapsack problems"],"prefix":"10.1007","volume":"279","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[]},{"given":"Areg","family":"Karapetyan","sequence":"additional","affiliation":[]},{"given":"Trung Thanh","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,6]]},"reference":[{"issue":"4","key":"3111_CR1","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1145\/320211.320240","volume":"46","author":"S Basu","year":"1999","unstructured":"Basu, S. (1999). New results on quantifier elimination over real closed fields and applications to constraint databases. Journal of the ACM, 46(4), 537\u2013555.","journal-title":"Journal of the ACM"},{"issue":"3","key":"3111_CR2","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/S0377-2217(01)00179-5","volume":"138","author":"KM Bretthauer","year":"2002","unstructured":"Bretthauer, K. M., & Shetty, B. (2002). The nonlinear knapsack problem\u2014Algorithms and applications. European Journal of Operational Research, 138(3), 459\u2013472.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"3111_CR3","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(76)90048-7","volume":"3","author":"AK Chandra","year":"1976","unstructured":"Chandra, A. K., Hirschberg, D. S., & Wong, C. K. (1976). Approximate algorithms for some generalized knapsack problems. Theoretical Computer Science, 3(3), 293\u2013304.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"3111_CR4","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2955089","volume":"5","author":"C Chau","year":"2016","unstructured":"Chau, C., Elbassioni, K. M., & Khonji, M. (2016). Truthful mechanisms for combinatorial allocation of electric power in alternating current electric systems for smart grid. ACM Transactions on Economics and Computation, 5(1), 7:1\u20137:29.","journal-title":"ACM Transactions on Economics and Computation"},{"key":"3111_CR5","doi-asserted-by":"crossref","unstructured":"Chau, S. C., Elbassioni, K. M., & Khonji, M. (2014). Truthful mechanisms for combinatorial AC electric power allocation. In International conference on autonomous agents and multi-agent systems, AAMAS \u201914 (pp. 1005\u20131012), Paris, France, 5\u20139 May 2014.","DOI":"10.65109\/LVLK5622"},{"issue":"1\u20132","key":"3111_CR6","first-page":"15","volume":"10","author":"J Csirik","year":"1991","unstructured":"Csirik, J., Frenk, J. B. G., Labb\u00e9, M., & Zhang, S. (1991). Heuristic for the 0\u20131 min-knapsack problem. Acta Cybernetica, 10(1\u20132), 15\u201320.","journal-title":"Acta Cybernetica"},{"key":"3111_CR7","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.dam.2017.06.020","volume":"230","author":"KM Elbassioni","year":"2017","unstructured":"Elbassioni, K. M., & Nguyen, T. T. (2017). Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions. Discrete Applied Mathematics, 230, 56\u201370.","journal-title":"Discrete Applied Mathematics"},{"key":"3111_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W.H. Freeman."},{"key":"3111_CR9","unstructured":"Hedengren, J. D. (2014). APMonitor Modeling Language. http:\/\/APMonitor.com . Accessed 18 Aug 2017."},{"key":"3111_CR10","volume-title":"Resource allocation problems","author":"T Ibaraki","year":"1988","unstructured":"Ibaraki, T., & Katoh, N. (1988). Resource allocation problems. Cambridge, MA: MIT Press."},{"issue":"4","key":"3111_CR11","doi-asserted-by":"publisher","first-page":"2714","DOI":"10.1109\/TSG.2016.2616945","volume":"9","author":"A Karapetyan","year":"2018","unstructured":"Karapetyan, A., Khonji, M., Chau, C. K., Elbassioni, K., & Zeineldin, H. (2018). Efficient algorithm for scalable event-based demand response management in microgrids. IEEE Transactions on Smart Grid, 9(4), 2714\u20132725. https:\/\/doi.org\/10.1109\/TSG.2016.2616945 .","journal-title":"IEEE Transactions on Smart Grid"},{"key":"3111_CR12","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. (2004). Knapsack problems. Berlin: Springer."},{"issue":"4","key":"3111_CR13","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s00453-008-9248-1","volume":"57","author":"H Kellerer","year":"2010","unstructured":"Kellerer, H., & Strusevich, V. A. (2010). Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57(4), 769\u2013795.","journal-title":"Algorithmica"},{"issue":"2","key":"3111_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10288-011-0180-x","volume":"10","author":"H Kellerer","year":"2012","unstructured":"Kellerer, H., & Strusevich, V. A. (2012). The symmetric quadratic knapsack problem: approximation and scheduling applications. 4OR, 10(2), 111\u2013161.","journal-title":"4OR"},{"key":"3111_CR15","unstructured":"Khonji, M., Karapetyan, A., Elbassioni, K., & Chau, C. K. (2016). Complex-demand scheduling problem with application in smart grid. In Computing and combinatorics (pp. 496\u2013509). Berlin: Springer."},{"key":"3111_CR16","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and combinatorial optimization. New York, NY: Wiley-Interscience."},{"key":"3111_CR17","unstructured":"Pferschy, U., & Schauer, J. (2013). Approximating the quadratic knapsack problem on special graph classes. In Approximation and online algorithms\u201411th international workshop, WAOA 2013 (pp. 61\u201372), Sophia Antipolis, France, September 5\u20136, 2013, Revised selected papers."},{"issue":"6","key":"3111_CR18","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/0221060","volume":"21","author":"J Renegar","year":"1992","unstructured":"Renegar, J. (1992). On the computational complexity of approximating solutions for real algebraic formulae. SIAM Journal on Computing, 21(6), 1008\u20131025.","journal-title":"SIAM Journal on Computing"},{"key":"3111_CR19","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of linear and integer programming. New York: Wiley."},{"issue":"3","key":"3111_CR20","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"DJ Rader Jr","year":"2002","unstructured":"Rader, D. J, Jr., & Woeginger, G. J. (2002). The quadratic 0\u20131 knapsack problem with series-parallel support. Operations Research Letters, 30(3), 159\u2013166.","journal-title":"Operations Research Letters"},{"issue":"1","key":"3111_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"GJ Woeginger","year":"2000","unstructured":"Woeginger, G. J. (2000). When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing, 12(1), 57\u201374.","journal-title":"INFORMS Journal on Computing"},{"key":"3111_CR22","volume-title":"Power generation, operation, and control","author":"AJ Wood","year":"2012","unstructured":"Wood, A. J., & Wollenberg, B. F. (2012). Power generation, operation, and control. London: Wiley."},{"key":"3111_CR23","doi-asserted-by":"crossref","unstructured":"Yu, L., & Chau, C. (2013). Complex-demand knapsack problems and incentives in AC power systems. In International conference on autonomous agents and multi-agent systems, AAMAS \u201913 (pp. 973\u2013980), Saint Paul, MN, USA, May 6\u201310, 2013.","DOI":"10.65109\/BSEM1672"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-3111-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-018-3111-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-3111-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T09:36:06Z","timestamp":1775295366000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-018-3111-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,6]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["3111"],"URL":"https:\/\/doi.org\/10.1007\/s10479-018-3111-9","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,6]]},"assertion":[{"value":"6 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}