{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:01:25Z","timestamp":1783576885092,"version":"3.55.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,1,19]],"date-time":"2016-01-19T00:00:00Z","timestamp":1453161600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NL)","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council (BE)","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00453-016-0116-0","type":"journal-article","created":{"date-parts":[[2016,1,19]],"date-time":"2016-01-19T11:37:15Z","timestamp":1453203435000},"page":"1077-1096","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds"],"prefix":"10.1007","volume":"76","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8509-7002","authenticated-orcid":false,"given":"Tim","family":"Oosterwijk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruben","family":"van der Zwaan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,1,19]]},"reference":[{"key":"116_CR1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1, 55\u201366 (1998)","journal-title":"J. Sched."},{"key":"116_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Vredeveld, T., van der Zwaan, R.: Approximating vector scheduling: almost matching upper and lower bounds. In: Proceedings of 11th Latin American Symposium on Theoretical Informatics of Theoretical Computer Science and General Issues, vol. 8392, pp. 47\u201359. Springer, Berlin Heidelberg (2014)","DOI":"10.1007\/978-3-642-54423-1_5"},{"key":"116_CR3","unstructured":"Bonifaci, V., Wiese, A.: Scheduling unrelated machines of few different types. CoRR, abs\/1205.0974, (2012)"},{"key":"116_CR4","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In IEEE conference on computational complexity, pp. 252\u2013260. IEEE computer society, (2006)","DOI":"10.1109\/CCC.2006.6"},{"issue":"4","key":"116_CR5","first-page":"837","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. Soc. Ind. Appl. Math. J. Comput. 33(4), 837\u2013851 (2004)","journal-title":"Soc. Ind. Appl. Math. J. Comput."},{"issue":"5","key":"116_CR6","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/j.orl.2005.09.008","volume":"34","author":"F Eisenbrand","year":"2006","unstructured":"Eisenbrand, F., Shmonin, G.: Carath\u00e9odory bounds for integer cones. Oper. Res. Lett. 34(5), 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"116_CR7","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/S0196-6774(03)00055-5","volume":"48","author":"L Epstein","year":"2003","unstructured":"Epstein, L., Tassa, T.: Vector assignment problems: a general framework. J. Algorithm 48(2), 360\u2013384 (2003)","journal-title":"J. Algorithm"},{"issue":"6\u20137","key":"116_CR8","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s00236-005-0003-7","volume":"42","author":"L Epstein","year":"2006","unstructured":"Epstein, L., Tassa, T.: Vector assignment schemes for asymmetric settings. Acta Inform. 42(6\u20137), 501\u2013514 (2006)","journal-title":"Acta Inform."},{"key":"116_CR9","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, E.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"116_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"1","key":"116_CR11","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. Assoc. Comput. Mach. 34(1), 144\u2013162 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"116_CR12","first-page":"539","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. Soc. Ind. Appl. Math. J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"Soc. Ind. Appl. Math. J. Comput."},{"issue":"4","key":"116_CR13","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"116_CR14","first-page":"457","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. Soc. Ind. Appl. Math. J. Discret. Math. 24(2), 457\u2013485 (2010)","journal-title":"Soc. Ind. Appl. Math. J. Discret. Math."},{"issue":"3","key":"116_CR15","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"116_CR16","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. SFCS \u201982, pp. 312\u2013320. IEEE Computer Society, Washington, DC (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"4","key":"116_CR17","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"116_CR18","series-title":"Algorithms and Techniques, volume 8096 of Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-40328-6_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"A Meyerson","year":"2013","unstructured":"Meyerson, A., Roytman, A., Tagiku, B.: Online multidimensional load balancing. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 8096 of Lecture Notes in Computer Science, pp. 287\u2013302. Springer, Berlin Heidelberg (2013)"},{"key":"116_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"116_CR20","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: Approximating bin packing within O(log OPT * Log Log OPT) bins. In: IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 20\u201329. IEEE, Berkeley, CA (2013)","DOI":"10.1109\/FOCS.2013.11"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0116-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0116-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0116-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0116-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T16:36:20Z","timestamp":1567528580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0116-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,19]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["116"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0116-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,19]]}}}