{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:32:57Z","timestamp":1763663577121},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,30]],"date-time":"2017-05-30T00:00:00Z","timestamp":1496102400000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10878-017-0143-z","type":"journal-article","created":{"date-parts":[[2017,5,30]],"date-time":"2017-05-30T08:38:50Z","timestamp":1496133530000},"page":"1218-1236","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Change-making problems revisited: a parameterized point of view"],"prefix":"10.1007","volume":"34","author":[{"given":"Steffen","family":"Goebbels","sequence":"first","affiliation":[]},{"given":"Frank","family":"Gurski","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"Rethmann","sequence":"additional","affiliation":[]},{"given":"Eda","family":"Yilmaz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,30]]},"reference":[{"issue":"1","key":"143_CR1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejc.2009.05.002","volume":"31","author":"A Adamaszek","year":"2010","unstructured":"Adamaszek A, Adamaszek M (2010) Combinatorics of the change-making problem. Eur J Comb 31(1):47\u201363","journal-title":"Eur J Comb"},{"key":"143_CR2","first-page":"17","volume-title":"IWPEC 2009, volume 5917 of lecture notes in computer science","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender HL (2009) Kernelization: new upper and lower bound techniques. In: Chen J, Fomin FV (eds) IWPEC 2009, volume 5917 of lecture notes in computer science. Springer, Berlin, pp 17\u201337"},{"key":"143_CR3","doi-asserted-by":"crossref","unstructured":"Bringmann K (2017) A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. In: ACM-SIAM symposium on discrete algorithms, pp 1073\u20131084","DOI":"10.1137\/1.9781611974782.69"},{"key":"143_CR4","doi-asserted-by":"crossref","unstructured":"Cai X (2009) Canonical coin systems for CHANGE-MAKING problems. In: 9th international conference on hybrid intelligent systems (HIS 2009), Shenyang. IEEE, pp 499\u2013504","DOI":"10.1109\/HIS.2009.103"},{"issue":"1","key":"143_CR5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/321556.321567","volume":"17","author":"SK Chang","year":"1970","unstructured":"Chang SK, Gill A (1970) Algorithmic solution of the change-making problem. J ACM 17(1):113\u2013122","journal-title":"J ACM"},{"issue":"R90","key":"143_CR6","first-page":"1","volume":"15","author":"LJ Cowen","year":"2008","unstructured":"Cowen LJ, Cowen R, Steinberg A (2008) Totally greedy coin sets and greedy obstructions. Electron J Comb 15(R90):1\u201313","journal-title":"Electron J Comb"},{"key":"143_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, New York"},{"issue":"1\u20132","key":"143_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor Comput Sci 141(1\u20132):109\u2013131","journal-title":"Theor Comput Sci"},{"key":"143_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin"},{"key":"143_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Springer, New York"},{"key":"143_CR11","doi-asserted-by":"crossref","unstructured":"Etscheid M, Kratsch S, Mnich M, R\u00f6glin H (2015) Polynomial kernels for weighted problems. In: Mathematical foundations of computer science. Lecture notes in computer science, vol. 673. Springer, Berlin, pp 287\u2013298","DOI":"10.1007\/978-3-662-48054-0_24"},{"key":"143_CR12","doi-asserted-by":"crossref","unstructured":"Fellows MR, Koblitz N (1993) Fixed-parameter complexity and cryptography. In: Conference applied algebra, algebraic algorithms and error-correcting codes (1993), volume 673 of lecture notes in computer science. Springer, Berlin, pp 121\u2013131","DOI":"10.1007\/3-540-56686-4_38"},{"key":"143_CR13","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin"},{"issue":"1","key":"143_CR14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank A, Tardos E (1987) An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1):49\u201365","journal-title":"Combinatorica"},{"issue":"2","key":"143_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz E, Sahni S (1974) Computing partitions with applications to the knapsack problem. J ACM 21(2):277\u2013292","journal-title":"J ACM"},{"issue":"1","key":"143_CR16","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1287\/opre.24.1.193","volume":"24","author":"TC Hu","year":"1976","unstructured":"Hu TC, Lenard ML (1976) Optimality of a heuristic solution for a class of knapsack problems. Oper Res 24(1):193\u2013196","journal-title":"Oper Res"},{"key":"143_CR17","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan R (1987) Minkowski\u2019s convex body theorem and integer programming. Math Oper Res 12:415\u2013440","journal-title":"Math Oper Res"},{"key":"143_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103"},{"key":"143_CR19","doi-asserted-by":"crossref","unstructured":"Koiliaris K, Xu C (2017) A faster pseudopolynomial time algorithm for subset sum. In: ACM-SIAM symposium on discrete algorithms, pp 1062\u20131072","DOI":"10.1137\/1.9781611974782.68"},{"key":"143_CR20","unstructured":"Lueker GS (1975) Two NP-complete problems in nonnegative integer programming. Technical Report 178, Department of Computer Science, Princeton University, Princeton, N.J"},{"issue":"2","key":"143_CR21","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1287\/opre.23.2.207","volume":"23","author":"MJ Magazine","year":"1975","unstructured":"Magazine MJ, Nemhauser GL, Trotter LE Jr (1975) When the greedy solution solves a class of knapsack problems. Oper Res 23(2):207\u2013217","journal-title":"Oper Res"},{"key":"143_CR22","volume-title":"Knapsack problems","author":"S Martello","year":"1990","unstructured":"Martello S, Toth P (1990) Knapsack problems. John Wiley & Sons, New York"},{"key":"143_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, New York"},{"issue":"3","key":"143_CR24","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.orl.2004.06.001","volume":"33","author":"D Pearson","year":"2005","unstructured":"Pearson D (2005) A polynomial-time algorithm for the change-making problem. Oper Res Lett 33(3):231\u2013234","journal-title":"Oper Res Lett"},{"issue":"1","key":"143_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1999.1034","volume":"33","author":"D Pisinger","year":"1999","unstructured":"Pisinger D (1999) Linear time algorithms for knapsack problems with bounded weights. J Algorithms 33(1):1\u201314","journal-title":"J Algorithms"},{"issue":"1","key":"143_CR26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1145\/321864.321874","volume":"22","author":"JW Wright","year":"1975","unstructured":"Wright JW (1975) The change-making problem. J ACM 22(1):125\u2013128","journal-title":"J ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0143-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0143-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0143-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T11:45:08Z","timestamp":1507549508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0143-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,30]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["143"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0143-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,30]]}}}