{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:44Z","timestamp":1740109424032,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T00:00:00Z","timestamp":1555891200000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00224-019-09917-z","type":"journal-article","created":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T07:02:35Z","timestamp":1555916555000},"page":"17-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Clever Shopper Problem"],"prefix":"10.1007","volume":"64","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9945-6774","authenticated-orcid":false,"given":"Anthony","family":"Labarre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,22]]},"reference":[{"issue":"1","key":"9917_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3330137","volume":"24","author":"Kate\u0159ina Altmanov\u00e1","year":"2019","unstructured":"Altmanov\u00e1, K., Knop, D., Kouteck\u00fd, M.: Evaluating and tuning n-fold integer programming. In: D\u2019Angelo, G. (ed.) 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L\u2019Aquila, Italy, vol. 103 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 10:1\u201310:14 (2018)","journal-title":"Journal of Experimental Algorithmics"},{"key":"9917_CR2","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"S Assmann","year":"1984","unstructured":"Assmann, S., Johnson, D., Kleitman, D., Leung, J.-T.: On a dual version of the one-dimensional bin packing problem. J. Algorithms 5, 502\u2013525 (1984)","journal-title":"J. Algorithms"},{"key":"9917_CR3","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT electronic colloquium on computational complexity (ECCC) (2003)"},{"key":"9917_CR4","first-page":"385","volume":"20","author":"J Blazewicz","year":"2010","unstructured":"Blazewicz, J., Kovalyov, M.Y., Musial, J., Urbanski, A.P., Wojciechowski, A.: Internet shopping optimization problem. Appl. Math. Comput. Sci. 20, 385\u2013390 (2010)","journal-title":"Appl. Math. Comput. Sci."},{"key":"9917_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10288-013-0230-7","volume":"12","author":"J Blazewicz","year":"2014","unstructured":"Blazewicz, J., Bouvry, P., Kovalyov, M.Y., Musial, J.: Internet shopping with price sensitive discounts. 4OR 12, 35\u201348 (2014)","journal-title":"4OR"},{"key":"9917_CR6","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10951-014-0390-0","volume":"19","author":"J Blazewicz","year":"2016","unstructured":"Blazewicz, J., Cheriere, N., Dutot, P.-F., Musial, J., Trystram, D.: Novel dual discounting functions for the internet shopping optimization problem: new algorithms. J. Sched. 19, 245\u2013255 (2016)","journal-title":"J. Sched."},{"key":"9917_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28, 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"9917_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-90530-3_6","volume-title":"Computer Science \u2013 Theory and Applications","author":"Laurent Bulteau","year":"2018","unstructured":"Bulteau, L., Hermelin, D., Labarre, A., Vialette, S.: The clever shopper problem. In: Fomin, F.V., Podolskii, V.V. (eds.) Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, Proceedings, vol. 10846 of Lecture Notes in Computer Science, pp. 53\u201364. Springer, Berlin (2018)"},{"key":"9917_CR9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00207-1","volume":"81","author":"M Cesati","year":"2002","unstructured":"Cesati, M.: Perfect code is W[1]-complete. Inf. Process. Lett. 81, 163\u2013168 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9917_CR10","unstructured":"Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.): 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, vol. 107 of LIPIcs Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"9917_CR11","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"Jack Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math., 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"9917_CR12","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: Chatzigiannakis et al. [10], pp. 49:1\u201349:13"},{"key":"9917_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0020-0190(76)90012-0","volume":"5","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N.: A note on degree-constrained star subgraphs of bipartite graphs. Inf. Process. Lett. 5, 165\u2013167 (1976)","journal-title":"Inf. Process. Lett."},{"key":"9917_CR14","first-page":"293","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Comput. Sci."},{"key":"9917_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-011-0490-y","volume":"137","author":"R Hemmecke","year":"2013","unstructured":"Hemmecke, R., Onn, S., Romanchuk, L.: N-fold integer programming in cubic time. Math. Program. 137, 325\u2013341 (2013)","journal-title":"Math. Program."},{"key":"9917_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79, 39\u201349 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"9917_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85\u2013103, Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9917_CR18","unstructured":"Knop, D., Kouteck\u00fd, M., Mnich, M.: Combinatorial n-fold integer programming and applications. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, vol. 87 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 54:1\u201354:14 (2017)"},{"key":"9917_CR19","unstructured":"Kouteck\u00fd, M, Levin, A, Onn, S: A parameterized strongly polynomial algorithm for block structured integer programs, In: Chatzigiannakis et al. [10], pp. 85:1\u201385:14"},{"key":"9917_CR20","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.artint.2016.08.001","volume":"240","author":"R Bevern van","year":"2016","unstructured":"van Bevern, R., Komusiewicz, C., Niedermeier, R., Sorge, M., Walsh, T.: H-index manipulation by merging articles: models, theory, and experiments. Artif. Intell. 240, 19\u201335 (2016)","journal-title":"Artif. Intell."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09917-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09917-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09917-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T23:07:39Z","timestamp":1587424059000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09917-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,22]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9917"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09917-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,4,22]]},"assertion":[{"value":"22 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}