{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:01Z","timestamp":1770994081969,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319905297","type":"print"},{"value":"9783319905303","type":"electronic"}],"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-90530-3_26","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"308-320","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["On Strong NP-Completeness of Rational Problems"],"prefix":"10.1007","author":[{"given":"Dominik","family":"Wojtczak","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"issue":"4","key":"26_CR1","first-page":"761","volume":"221","author":"LG Babat","year":"1975","unstructured":"Babat, L.G.: Linear functions on n-dimensional unit cube. Doklady Akademii Nauk SSSR 221(4), 761\u2013762 (1975)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"3","key":"26_CR2","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":"26_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"issue":"2","key":"26_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10472-009-9162-5","volume":"56","author":"E Elkind","year":"2009","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: On the computational complexity of weighted voting games. Ann. Math. Artif. Intell. 56(2), 109\u2013131 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/BFb0120892","volume-title":"Combinatorial Optimization","author":"G Gallo","year":"1980","unstructured":"Gallo, G., Hammer, P.L., Simeone, B.: Quadratic knapsack problems. In: Padberg, M.W. (ed.) Combinatorial Optimization, pp. 132\u2013149. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/BFb0120892"},{"issue":"3","key":"26_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: \u201cStrong\u201d NP-completeness results: motivation, examples, and implications. J. ACM (JACM) 25(3), 499\u2013508 (1978)","journal-title":"J. ACM (JACM)"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1023\/A:1018930613891","volume":"92","author":"C Gu\u00e9ret","year":"1999","unstructured":"Gu\u00e9ret, C., Prins, C.: A new lower bound for the open-shop problem. Ann. Oper. Res. 92, 165\u2013183 (1999)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"26_CR8","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/opre.42.1.102","volume":"42","author":"JA Hoogeveen","year":"1994","unstructured":"Hoogeveen, J.A., Oosterhout, H., van de Velde, S.L.: New lower and upper bounds for scheduling around a small common due date. Oper. Res. 42(1), 102\u2013110 (1994)","journal-title":"Oper. Res."},{"issue":"4","key":"26_CR9","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)"},{"issue":"1","key":"26_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.8.1.1","volume":"8","author":"DS Johnson","year":"1983","unstructured":"Johnson, D.S., Niemi, K.A.: On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8(1), 1\u201314 (1983)","journal-title":"Math. Oper. Res."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complex. Comput. Comput.","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complex. Comput. Comput., pp. 85\u2013103. Springer, Heidelberg (1972)"},{"key":"26_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.: Knapsack Problems. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7"},{"issue":"3","key":"26_CR13","first-page":"115","volume":"9","author":"LA Levin","year":"1973","unstructured":"Levin, L.A.: Universal sequential search problems. Problemy Peredachi Informatsii 9(3), 115\u2013116 (1973)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"1","key":"26_CR14","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1112\/plms\/s1-28.1.486","volume":"1","author":"GB Mathews","year":"1897","unstructured":"Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. 1(1), 486\u2013490 (1897)","journal-title":"Proc. Lond. Math. Soc."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Mousa, M.A.A., Schewe, S., Wojtczak, D.: Optimal control for simple linear hybrid systems. In: Proceedings of TIME, pp. 12\u201320. IEEE Computer Society (2016)","DOI":"10.1109\/TIME.2016.9"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-319-65765-3_5","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"MAA Mousa","year":"2017","unstructured":"Mousa, M.A.A., Schewe, S., Wojtczak, D.: Optimal control for multi-mode systems with discrete costs. In: Abate, A., Geeraerts, G. (eds.) FORMATS 2017. LNCS, vol. 10419, pp. 77\u201396. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-65765-3_5"},{"issue":"2","key":"26_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233\u2013249 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"26_CR18","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/S0377-2217(98)00120-9","volume":"114","author":"D Pisinger","year":"1999","unstructured":"Pisinger, D.: An exact algorithm for large multiple knapsack problems. Eur. J. Oper. Res. 114(3), 528\u2013541 (1999)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"26_CR19","first-page":"64","volume":"6","author":"JB Rosser","year":"1962","unstructured":"Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Ill. J. Math. 6(1), 64\u201394 (1962)","journal-title":"Ill. J. Math."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"26_CR21","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"M Silvano","year":"1990","unstructured":"Silvano, M., Paolo, T.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Hoboken (1990)"},{"issue":"1","key":"26_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8(1), 85\u201389 (1984)","journal-title":"Discrete Appl. Math."},{"key":"26_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer Science & Business Media, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"}],"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-319-90530-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T11:31:09Z","timestamp":1710243069000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","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":"Moscow","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":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}