Temporary tasks assignment resolved

ABSTRACT

Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin El-Yaniv]. We resolve this problem by providing an unapproximability result. In addition, a newer open question is to identify the dependency of the competitive ratio on the durations of jobs in the case where durations are known. We resolve this problem by characterizing this dependency. Finally, we provide a PTAS for the off-line problem with a fixed number of machines and show a 2 unapproximability for the general case.

REFERENCES

• 1: Susanne Albers, Better bounds for online scheduling, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.130-139, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258566]
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
• 3: Yossi Azar, On-line Load Balancing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.178-195, January 1998
• 4: Yossi Azar , Andrei Z. Broder , Anna R. Karlin, On-line load balancing, Theoretical Computer Science, v.130 n.1, p.73-84, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90153-8]
• 5: Yossi Azar , Leah Epstein, On-Line Load Balancing of Temporary Tasks on Identical Machines, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.119, June 17-19, 1997
• 6: Yossi Azar , Bala Kalyanasundaram , Serge Plotkin , Kirk R. Pruhs , Orli Waarts, On-line load balancing of temporary tasks, Journal of Algorithms, v.22 n.1, p.93-110, Jan. 1997 [doi>10.1006/jagm.1995.0799]
• 7: Yossi Azar , Joseph Seffi Naor , Raphael Rom, The competitiveness of on-line assignments, Journal of Algorithms, v.18 n.2, p.221-237, March 1995 [doi>10.1006/jagm.1995.1008]
• 8: Yossi Azar , Oded Regev, Off-Line Temporary Tasks Assignment, Proceedings of the 7th Annual European Symposium on Algorithms, p.163-171, July 16-18, 1999
• 9: B. S. Baker, D. J. Brown, and H. P. Katseff. A 5/4 algorithm for two-dimensional packing. J. Algorithms, 2:348-368, 1981.
• 10: Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.51-58, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129718]
• 11: Piotr Berman , Moses Charikar , Marek Karpinski, On-line Load Balancing for Related Machines, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.116-125, August 06-08, 1997
• 12: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 13: B. Chen, A. van Vliet, and G. J. Woeginger. New lower and upper bounds for on-line scheduling. Operations Research Letters, 16:221-230, 1994.
• 14: W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1:349-355, 1981.
• 15: M. R. Garey, R. L. Graham, D. S. Johnson, and A. C. C. Yao. Resource constrained scheduling as generalized bin packing. J. Comb. Th. Ser. A., 21:257-298, 1976.
• 16: R. L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.
• 17: Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
• 18: David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.132-140, January 23-25, 1994, Arlington, Virginia, United States
• 19: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 20: Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167201]
• 21: Yuan Ma , Serge Plotkin, An improved lower bound for load balancing of tasks with unknown duration, Information Processing Letters, v.62 n.6, p.301-303, June 27, 1997 [doi>10.1016/S0020-0190(97)00085-9]
• 22: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 23: Jeffery Westbrook, Load Balancing for Response Time, Proceedings of the Third Annual European Symposium on Algorithms, p.355-368, September 25-27, 1995