{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:05:29Z","timestamp":1760079929823},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662491911"},{"type":"electronic","value":"9783662491928"}],"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-662-49192-8_24","type":"book-chapter","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T15:47:27Z","timestamp":1452181647000},"page":"290-301","source":"Crossref","is-referenced-by-count":7,"title":["A PTAS for Scheduling Unrelated Machines of Few Different Types"],"prefix":"10.1007","author":[{"given":"Jan Clemens","family":"Gehrke","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Stefan E. J.","family":"Kraft","sequence":"additional","affiliation":[]},{"given":"Jakob","family":"Schikowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"unstructured":"Arad, D., Mordechai, Y., Shachnai, H.: Tighter Bounds for Makespan Minimization on Unrelated Machines (2014). \n                      arXiv:1405.2530","key":"24_CR1"},{"doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Krishnaswamy, R., Talwar, K., Wieder, U.: Minimum makespan scheduling with low rank processing times. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 937\u2013947. SIAM (2013)","key":"24_CR2","DOI":"10.1137\/1.9781611973105.67"},{"issue":"6","key":"24_CR3","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1002\/cpe.3359","volume":"27","author":"R Bleuse","year":"2015","unstructured":"Bleuse, R., Kedad-Sidhoum, S., Monna, F., Mouni\u00e9, G., Trystram, D.: Scheduling independent tasks on multi-cores with GPU accelerators. Concurr. Comput. 27(6), 1625\u20131638 (2015)","journal-title":"Concurr. Comput."},{"unstructured":"Bonifaci, V., Wiese, A.: Scheduling Unrelated Machines of Few Different Types (2012). \n                      arXiv:1205.0974","key":"24_CR4"},{"doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Khanna, S., Li, S.: On \n                      \n                        \n                      \n                      $$(1,\\varepsilon )$$\n                    -restricted assignment makespan minimization. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1087\u20131101. SIAM (2015)","key":"24_CR5","DOI":"10.1137\/1.9781611973730.73"},{"issue":"5","key":"24_CR6","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.orl.2014.06.003","volume":"42","author":"L Chen","year":"2014","unstructured":"Chen, L., Ye, D., Zhang, G.: An improved lower bound for rank four scheduling. Oper. Res. Lett. 42(5), 348\u2013350 (2014)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00453-007-9086-6","volume":"51","author":"AV Fishkin","year":"2008","unstructured":"Fishkin, A.V., Jansen, K., Mastrolilli, M.: Grouping techniques for scheduling problems: simpler and faster. Algorithmica 51(2), 183\u2013199 (2008)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"24_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2007.02.056","volume":"380","author":"M Gairing","year":"2007","unstructured":"Gairing, M., Monien, B., Woclaw, A.: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theor. Comput. Sci. 380(1\u20132), 87\u201399 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR9","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)"},{"unstructured":"Gehrke, J.C., Jansen, K., Kraft, S.E.J., Schikowski, J.: A PTAS for Scheduling Unrelated Machines of Few Different Types. Technical report, No. 1506, Christian-Albrechts-Universit\u00e4t zu Kiel (2015). ISSN 2192-6247","key":"24_CR10"},{"key":"24_CR11","first-page":"287","volume-title":"Discrete Optimization II, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and V","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P.L., Johnson, E.L., Korte, B.H. (eds.) Discrete Optimization II: Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Annals of Discrete Mathematics, vol. 5, pp. 287\u2013326. Elsevier (1979)"},{"issue":"1","key":"24_CR12","doi-asserted-by":"publisher","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(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"24_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","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. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"issue":"4","key":"24_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s00607-003-0011-9","volume":"70","author":"C Imreh","year":"2003","unstructured":"Imreh, C.: Scheduling problems on two sets of identical machines. Computing 70(4), 277\u2013294 (2003)","journal-title":"Computing"},{"issue":"2","key":"24_CR16","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1287\/moor.26.2.324.10559","volume":"26","author":"K Jansen","year":"2001","unstructured":"Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. Math. Oper. Res. 26(2), 324\u2013338 (2001)","journal-title":"Math. Oper. Res."},{"key":"24_CR17","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)"},{"unstructured":"Jansen, K., Mastrolilli, M.: Scheduling unrelated parallel machines: linear rogramming strikes back. Christian-Albrechts-Universit\u00e4t zu Kiel (2010). ISSN: 2192-6247,\u00a0No. 1004","key":"24_CR18"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"doi-asserted-by":"crossref","unstructured":"Raravi, G., N\u00e9lis, V.: A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors. In: Proceedings of the 33rd IEEE Real-Time Systems Symposium, RTSS 2012, pp. 117\u2013126. IEEE Computer Society (2012)","key":"24_CR20","DOI":"10.1109\/RTSS.2012.64"},{"issue":"2","key":"24_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"EV Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33(2), 127\u2013133 (2005)","journal-title":"Oper. Res. Lett."},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"issue":"5","key":"24_CR23","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1137\/110851201","volume":"41","author":"O Svensson","year":"2012","unstructured":"Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318\u20131341 (2012)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s11241-012-9164-y","volume":"49","author":"A Wiese","year":"2013","unstructured":"Wiese, A., Bonifaci, V., Baruah, S.K.: Partitioned EDF scheduling on a few types of unrelated multiprocessors. Real-Time Syst. 49(2), 219\u2013238 (2013)","journal-title":"Real-Time Syst."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2016: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49192-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T08:47:54Z","timestamp":1559378874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49192-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662491911","9783662491928"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49192-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}