{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:04Z","timestamp":1759637704772},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_44","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T08:16:59Z","timestamp":1477815419000},"page":"608-623","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints"],"prefix":"10.1007","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Wenchang","family":"Luo","sequence":"additional","affiliation":[]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"44_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":"44_CR2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01193837","volume":"47","author":"L Babel","year":"1998","unstructured":"Babel, L., Kellerer, H., Kotov, V.: The $$k$$ -partitioning problem. Math. Methods Oper. Res. 47, 59\u201382 (1998)","journal-title":"Math. Methods Oper. Res."},{"key":"44_CR3","unstructured":"Barna, S., Aravind, S.: A new approximation technique for resource-allocation problems. In: Proceedings of the 1st Annual Symposium on Innovations in Computer Science, pp. 342\u2013357 (2010)"},{"issue":"9","key":"44_CR4","doi-asserted-by":"crossref","first-page":"1344","DOI":"10.1016\/j.dam.2005.05.036","volume":"154","author":"M Bruglieri","year":"2006","unstructured":"Bruglieri, M., Ehrgott, M., Hamacher, H.W., Maffioli, F.: An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. Discret. Appl. Math. 154(9), 1344\u20131357 (2006)","journal-title":"Discret. Appl. Math."},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Chen, L., Jansen, K., Zhang, G.C.: On the optimality of approximation schemes for the classical scheduling problem. In: Proceedings of SODA 2014, pp. 657\u2013668 (2014)","DOI":"10.1137\/1.9781611973402.50"},{"key":"44_CR6","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1016\/j.ejor.2004.09.002","volume":"171","author":"M Dell\u2019Amico","year":"2004","unstructured":"Dell\u2019Amico, M., Lori, M., Martello, S., Monaci, M.: Lower bounds and heuristic algorithms for the $$k_i$$ -partitioning problem. Eur. J. Oper. Res. 171, 725\u2013742 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"44_CR7","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.: Caratheodory bounds for integer cones. Oper. Res. Lett. 34, 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"key":"44_CR8","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. ACM 34, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"44_CR9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"44_CR10","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/090749451","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. SIAM J. Discret. Math. 24, 457\u2013485 (2010)","journal-title":"SIAM J. Discret. Math."},{"key":"44_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-29116-6_10","volume-title":"Approximation and Online Algorithms","author":"K Jansen","year":"2012","unstructured":"Jansen, K., Robenek, C.: Scheduling jobs on identical and uniform processors revisited. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 109\u2013122. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-29116-6_10"},{"key":"44_CR12","unstructured":"Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: Proceedings of ICALP, pp. 72:1\u201372:13 (2016)"},{"key":"44_CR13","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, 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"44_CR14","first-page":"359","volume":"39","author":"H Kellerer","year":"2011","unstructured":"Kellerer, H., Kotov, V.: A 3\/2-approximation algorithm for $$k_i$$ -partitioning. Oper. Res. Lett. 39, 359\u2013362 (2011)","journal-title":"Oper. Res. Lett."},{"key":"44_CR15","first-page":"48","volume":"37","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H., Kotov, V.: A 7\/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling. Inf. Syst. Oper. Res. 37, 48\u201356 (1999)","journal-title":"Inf. Syst. Oper. Res."},{"key":"44_CR16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0166-218X(93)90013-E","volume":"45","author":"H Kellerer","year":"1993","unstructured":"Kellerer, H., Woeginger, G.: A tight bound for 3-partitioning. Discret. Appl. Math. 45, 249\u2013259 (1993)","journal-title":"Discret. Appl. Math."},{"key":"44_CR17","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/opre.36.2.192","volume":"36","author":"MJ Magazine","year":"1988","unstructured":"Magazine, M.J., Ball, M.O.: Sequencing of insertions in printed circuit board assembly. Oper. Res. 36, 192\u2013201 (1988)","journal-title":"Oper. Res."},{"key":"44_CR18","unstructured":"Rushmeier, R.A., Hoffman, K.L., Padberg, M.: Recent advances in exact optimization of airline scheduling problems. Technical report, George Mason University (1995)"},{"key":"44_CR19","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/j.disopt.2005.06.005","volume":"2","author":"G Woeginger","year":"2005","unstructured":"Woeginger, G.: A comment on scheduling two parallel machines with capacity constraints. Discret. Optim. 2, 269\u2013272 (2005)","journal-title":"Discret. Optim."},{"key":"44_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-02270-8_29","volume-title":"Frontiers in Algorithmics","author":"C Zhang","year":"2009","unstructured":"Zhang, C., Wang, G., Liu, X., Liu, J.: Approximating scheduling machines with capacity constraints. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) FAW 2009. LNCS, vol. 5598, pp. 283\u2013292. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02270-8_29"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T02:24:37Z","timestamp":1498357477000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}