{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T17:49:06Z","timestamp":1695577746902},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,25]],"date-time":"2016-05-25T00:00:00Z","timestamp":1464134400000},"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":["Optim Lett"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s11590-016-1043-3","type":"journal-article","created":{"date-parts":[[2016,5,25]],"date-time":"2016-05-25T14:53:45Z","timestamp":1464188025000},"page":"31-39","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Knapsack problem with objective value gaps"],"prefix":"10.1007","volume":"11","author":[{"given":"Alexander","family":"Dolgui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail Y.","family":"Kovalyov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Quilliot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"1043_CR1","series-title":"Part I, LNCS 7965","first-page":"1","volume-title":"ICALP 2013","author":"A Abboud","year":"2013","unstructured":"Abboud, A., Lewi, K.: Exact weight subgraphs and the k-sum conjecture. In: Fomin, F.V., et al. (eds.) ICALP 2013. Part I, LNCS 7965, pp. 1\u201312. Springer-Verlag, Berlin Heidelberg (2013)"},{"key":"1043_CR2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0166-218X(87)90067-9","volume":"16","author":"F Barahona","year":"1987","unstructured":"Barahona, F., Pulleyblank, W.R.: Exact aborescences, matchings and cycles. Discrete Appl. Math. 16, 91\u201399 (1987)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1043_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/13094774X","volume":"25","author":"N Halman","year":"2015","unstructured":"Halman, N., Nannicini, G., Orlin, J.: A computationally efficient FPTAS for convex stochastic dynamic programs. SIAM J. Optim. 25(1), 317\u2013350 (2015)","journal-title":"SIAM J. Optim."},{"key":"1043_CR4","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17, 36\u201342 (1992)","journal-title":"Math. Oper. Res."},{"key":"1043_CR5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0022-247X(66)90020-5","volume":"14","author":"HC Joksch","year":"1966","unstructured":"Joksch, H.C.: The shortest route problem with constraints. J. Math. Anal. Appl. 14, 191\u2013197 (1966)","journal-title":"J. Math. Anal. Appl."},{"key":"1043_CR6","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BF01068796","volume":"23","author":"AV Karzanov","year":"1987","unstructured":"Karzanov, A.V.: Maximum matching of given weight in complete and complete bipartite graphs. Cybernetics 23, 8\u201313 (1987). (Translation from Kibernetika 1, 7\u201311 (1987), in Russian)","journal-title":"Cybernetics"},{"key":"1043_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/A:1009813105532","volume":"3","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. J. Comb. Optim. 3, 59\u201371 (1999)","journal-title":"J. Comb. Optim."},{"key":"1043_CR8","doi-asserted-by":"crossref","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, Berlin (2004)"},{"key":"1043_CR9","unstructured":"Leclerc, M.: Polynomial time algorithms for exact matching problems, Masters Thesis, University of Waterloo, Waterloo (1986)"},{"issue":"3","key":"1043_CR10","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1007\/s11590-013-0637-2","volume":"8","author":"W Li","year":"2014","unstructured":"Li, W., Li, J.: Approximation algorithms for k-partitioning problems with partition matroid constraint. Optim. Lett. 8(3), 1093\u20131099 (2014)","journal-title":"Optim. Lett."},{"key":"1043_CR11","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)"},{"key":"1043_CR12","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.endm.2009.11.052","volume":"35","author":"M Milanic","year":"2009","unstructured":"Milanic, M., Monnot, J.: The exact weighted independent set problem in perfect graphs and related graph classes. Electron. Notes Discrete Math. 35, 317\u2013322 (2009)","journal-title":"Electron. Notes Discrete Math."},{"issue":"7","key":"1043_CR13","doi-asserted-by":"crossref","first-page":"1805","DOI":"10.1109\/TC.2014.2346178","volume":"64","author":"THC Nguyen","year":"2015","unstructured":"Nguyen, T.H.C., Richard, P., Grolleau, E.: An FPTAS for response time analysis of fixed priority real-time tasks with resource augmentation. IEEE Trans. Comput. 64(7), 1805\u20131818 (2015)","journal-title":"IEEE Trans. Comput."},{"key":"1043_CR14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29, 285\u2013309 (1982)","journal-title":"J. ACM"},{"issue":"6","key":"1043_CR15","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1287\/opre.25.6.920","volume":"25","author":"S Sahni","year":"1977","unstructured":"Sahni, S.: General techniques for combinatorial approximation. Oper. Res. 25(6), 920\u2013936 (1977)","journal-title":"Oper. Res."},{"key":"1043_CR16","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1287\/opre.26.5.718","volume":"26","author":"S Sahni","year":"1978","unstructured":"Sahni, S., Horowitz, E.: Combinatorial problems: reducibility and approximation. Oper. Res. 26, 718\u2013759 (1978)","journal-title":"Oper. Res."},{"key":"1043_CR17","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.amc.2014.11.062","volume":"255","author":"R Samanta","year":"2015","unstructured":"Samanta, R., Erzin, A.I., Raha, S., Shamardin, Y.V., Takhonov, I.I., Zalyubovskiy, V.V.: A provably tight delay-driven concurrently congestion mitigating global routing algorithm. Appl. Math. Comput. 255, 92\u2013104 (2015)","journal-title":"Appl. Math. Comput."},{"issue":"4","key":"1043_CR18","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1016\/j.cie.2013.04.002","volume":"65","author":"K Schemeleva","year":"2013","unstructured":"Schemeleva, K., Delorme, X., Dolgui, A., Grimaud, F., Kovalyov, M.Y.: Lot-sizing on a single imperfect machine: ILP models and FPTAS extensions. Comput. Ind. Eng. 65(4), 561\u2013569 (2013)","journal-title":"Comput. Ind. Eng."},{"key":"1043_CR19","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: Mitzenmacher, M. (ed.), STOC, pp. 455\u2013464. Association for Computing Machinery (2009)","DOI":"10.1145\/1536414.1536477"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1043-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-016-1043-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1043-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1043-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T13:11:45Z","timestamp":1559394705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-016-1043-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,25]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["1043"],"URL":"https:\/\/doi.org\/10.1007\/s11590-016-1043-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,25]]}}}