{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:01:21Z","timestamp":1783576881313,"version":"3.55.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T00:00:00Z","timestamp":1340323200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00453-012-9668-9","type":"journal-article","created":{"date-parts":[[2012,6,21]],"date-time":"2012-06-21T18:56:05Z","timestamp":1340304965000},"page":"62-80","source":"Crossref","is-referenced-by-count":34,"title":["Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines"],"prefix":"10.1007","volume":"68","author":[{"given":"Tom\u00e1\u0161","family":"Ebenlendr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Kr\u010d\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,6,22]]},"reference":[{"key":"9668_CR1","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1007\/978-3-540-85363-3_2","volume-title":"Approximation, Randomization and Combinatorial Optimization: Proc. of the 11th Int. Workshop APPROX 2008 and 12th Int. Workshop RANDOM","author":"A. Asadpour","year":"2008","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa Claus meets hypergraph matchings. In: Approximation, Randomization and Combinatorial Optimization: Proc. of the 11th Int. Workshop APPROX 2008 and 12th Int. Workshop RANDOM. Lecture Notes in Comput. Sci., vol.\u00a05171, pp.\u00a010\u201320. Springer, Berlin (2008)"},{"key":"9668_CR2","doi-asserted-by":"crossref","first-page":"2970","DOI":"10.1137\/080723491","volume":"39","author":"A. Asadpour","year":"2010","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39, 2970\u20132989 (2010)","journal-title":"SIAM J. Comput."},{"key":"9668_CR3","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1142\/S0129054111008246","volume":"22","author":"Y. Asahiro","year":"2011","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Graph orientation to maximize the minimum weighted outdegree. Int. J. Found. Comput. Sci. 22, 583\u2013601 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9668_CR4","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-540-72870-2_16","volume-title":"Proc. 2nd International Conf. on Algorithmic Aspects in Information and Management (AAIM)","author":"Y. Asahiro","year":"2007","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. In: Proc. 2nd International Conf. on Algorithmic Aspects in Information and Management (AAIM). Lecture Notes in Comput. Sci., vol.\u00a04508, pp.\u00a0167\u2013177. Springer, Berlin (2007)"},{"key":"9668_CR5","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/s10878-009-9276-z","volume":"22","author":"Y. Asahiro","year":"2011","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim. 22, 78\u201396 (2011)","journal-title":"J. Comb. Optim."},{"key":"9668_CR6","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/j.dam.2010.11.003","volume":"159","author":"Y. Asahiro","year":"2011","unstructured":"Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discrete Appl. Math. 159, 498\u2013508 (2011)","journal-title":"Discrete Appl. Math."},{"key":"9668_CR7","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1142\/S0129054107004644","volume":"18","author":"Y. Asahiro","year":"2007","unstructured":"Asahiro, Y., Miyano, E., Ono, H., Zenmyo, K.: Graph orientation algorithms to minimize the maximum outdegree. Int. J. Found. Comput. Sci. 18, 197\u2013215 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9668_CR8","first-page":"331","volume-title":"Proc. 37th Symp. Theory of Computing (STOC)","author":"Y. Azar","year":"2005","unstructured":"Azar, Y., Epstein, A.: Convex programming for scheduling unrelated parallel machines. In: Proc. 37th Symp. Theory of Computing (STOC), pp.\u00a0331\u2013337. ACM, New York (2005)"},{"key":"9668_CR9","first-page":"31","volume-title":"Proc. 38th Symp. Theory of Computing (STOC)","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proc. 38th Symp. Theory of Computing (STOC), pp.\u00a031\u201340. ACM, New York (2006)"},{"key":"9668_CR10","first-page":"543","volume-title":"Proc. 41st Symp. Theory of Computing (STOC)","author":"M. Bateni","year":"2009","unstructured":"Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proc. 41st Symp. Theory of Computing (STOC), pp.\u00a0543\u2013552. ACM, New York (2009)"},{"key":"9668_CR11","first-page":"107","volume-title":"Proc. 50th Symp. Foundations of Computer Science (FOCS)","author":"D. Chakrabarty","year":"2009","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proc. 50th Symp. Foundations of Computer Science (FOCS), pp.\u00a0107\u2013116. IEEE Press, New York (2009)"},{"key":"9668_CR12","first-page":"483","volume-title":"Proc. 19th Symp. on Discrete Algorithms (SODA)","author":"T. Ebenlendr","year":"2008","unstructured":"Ebenlendr, T., Kr\u010d\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: Proc. 19th Symp. on Discrete Algorithms (SODA), pp.\u00a0483\u2013490. ACM\/SIAM, New York (2008)"},{"key":"9668_CR13","doi-asserted-by":"crossref","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, 87\u201399 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9668_CR14","first-page":"397","volume-title":"Proc. 51st Symp. Foundations of Computer Science (FOCS)","author":"B. Haeupler","year":"2010","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovasz local lemma. In: Proc. 51st Symp. Foundations of Computer Science (FOCS), pp.\u00a0397\u2013406. IEEE Press, New York (2010)"},{"key":"9668_CR15","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S., Shmoys, D.: A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput. 17 (1988)","DOI":"10.1137\/0217033"},{"key":"9668_CR16","first-page":"317","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J.\u00a0ACM 23, 317\u2013327 (1976)","journal-title":"J.\u00a0ACM"},{"key":"9668_CR17","doi-asserted-by":"crossref","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, 324\u2013338 (2001)","journal-title":"Math. Oper. Res."},{"key":"9668_CR18","volume":"56","author":"V.S.A. Kumar","year":"2009","unstructured":"Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: A unified approach to scheduling on unrelated parallel machines. J. ACM 56, 28 (2009)","journal-title":"J. ACM"},{"key":"9668_CR19","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. 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."},{"key":"9668_CR20","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5","volume":"2","author":"P. Schuurman","year":"1999","unstructured":"Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: Ten open problems. J. Sched. 2, 203\u2013213 (1999)","journal-title":"J. Sched."},{"key":"9668_CR21","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"E.V. Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33, 127\u2013133 (2005)","journal-title":"Oper. Res. Lett."},{"key":"9668_CR22","first-page":"617","volume-title":"Proc. 43rd Symp. Theory of Computing (STOC)","author":"O. Svensson","year":"2011","unstructured":"Svensson, O.: Santa Claus schedules jobs on unrelated machines. In: Proc. 43rd Symp. Theory of Computing (STOC), pp.\u00a0617\u2013626. ACM, New York (2011)"},{"key":"9668_CR23","volume-title":"Approximation Algorithms","author":"V.V. Vazirany","year":"2001","unstructured":"Vazirany, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9668_CR24","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.dam.2003.07.007","volume":"143","author":"V. Venkateswaran","year":"2004","unstructured":"Venkateswaran, V.: Minimizing maximum indegree. Discrete Appl. Math. 143, 374\u2013378 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9668_CR25","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1007\/978-3-642-23719-5_45","volume-title":"Proc. 19th European Symp. on Algorithms (ESA)","author":"J. Verschae","year":"2011","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. In: Proc. 19th European Symp. on Algorithms (ESA). Lecture Notes in Comput. Sci., vol.\u00a06942, pp.\u00a0530\u2013542. Springer, Berlin (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9668-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9668-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9668-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,30]],"date-time":"2019-06-30T01:41:09Z","timestamp":1561858869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9668-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,22]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9668"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9668-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,22]]}}}