Coordination mechanisms for selfish scheduling

Theoretical Computer Science - Tập 410 - Trang 1589-1598 - 2009
Nicole Immorlica1, Li (Erran) Li2, Vahab S. Mirrokni3, Andreas S. Schulz4
1Northwestern University, Evanston, IL, United States
2Bell Labs, Murray Hill, NJ, United States
3Google Research, New York, NY, United States
4Massachusetts Institute of Technology, Cambridge, MA, United States

Tài liệu tham khảo

Aspnes, 1997, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM, 44, 486, 10.1145/258128.258201 Awerbuch, 2006, Tradeoffs in worst-case equilibria, Theoretical Computer Science, 361, 200, 10.1016/j.tcs.2006.05.010 Y. Azar, K. Jain, V.S. Mirrokni, (Almost) optimal coordination mechanisms for unrelated machine scheduling, in: Proceedings of the 19th Annual ACM–SIAM Symposium on Discrete Algorithms, 2008, pp. 323–332 Azar, 1995, The competitiveness of on-line assignments, Journal of Algorithms, 18, 221, 10.1006/jagm.1995.1008 Bagchi, 2004, vol. 64 Beckmann, 1956 Y. Bejerano, S.-J. Han, L. Li, Fairness and load balancing in wireless LANs using association control, in: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, 2004, pp. 315–329 Borst, 2005, User-level performance of channel-aware scheduling algorithms in wireless data networks, IEEE/ACM Transaction on Networking, 13, 636, 10.1109/TNET.2005.850215 Cho, 1980, Bounds for list schedules on uniform processors, SIAM Journal on Computing, 9, 91, 10.1137/0209007 Christodoulou, 2004, Coordination mechanisms, vol. 3142, 345 R. Cole, Y. Dodis, T. Roughgarden, How much can taxes help selfish routing? in: Proceedings of the 4th ACM Conference on Electronic Commerce, 2003, pp. 98–107 A. Czumaj, B. Vöcking, Tight bounds for worst-case equilibria, in: Proceedings of the 13th Annual ACM–SIAM Symposium on Discrete Algorithms, 2002, pp.413–420 Davis, 1981, Algorithms for scheduling tasks on unrelated processors, Journal of the ACM, 28, 721, 10.1145/322276.322284 Dobson, 1984, Scheduling independent tasks on uniform processors, SIAM Journal on Computing, 13, 705, 10.1137/0213044 Even-Dar, 2003, Convergence time to Nash equilibria, vol. 2719, 502 Finn, 1979, A linear time approximation algorithm for multiprocessor scheduling, BIT, 19, 312, 10.1007/BF01930985 L. Fleischer, K. Jain, M. Mahdian, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games, in: Proceedings of the 45th Symposium on Foundations of Computer Science, 2004, pp. 277–285 Friesen, 1987, Tighter bounds for LPT scheduling on uniform processors, SIAM Journal on Computing, 16, 554, 10.1137/0216037 M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, Computing Nash equilibria for scheduling on restricted parallel links, in: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 613–622 Goldenberg, 2004, Optimizing cost and performance for multihoming, ACM SIGCOMM Computer Communication Review, 34, 79, 10.1145/1030194.1015478 Graham, 1966, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45, 1563, 10.1002/j.1538-7305.1966.tb01709.x Graham, 1969, Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics, 17, 416, 10.1137/0117039 Ibarra, 1977, Heuristic algorithms for scheduling independent tasks on nonidentical processors, Journal of the ACM, 24, 280, 10.1145/322003.322011 Immorlica, 2005, Coordination mechanisms for selfish scheduling, vol. 3828, 55 Korilis, 1997, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking, 5, 161, 10.1109/90.554730 Koutsoupias, 1999, Worst-case equilibria, vol. 1563, 404 Lenstra, 1990, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46, 259, 10.1007/BF01585745 Moulin, 2007, On scheduling fees to prevent merging, splitting and transferring of jobs, Mathematics of Operations Research, 32, 266, 10.1287/moor.1060.0239 Nash, 1950, Equilibrium points in N-person games, Proceedings of the National Academy of Sciences of the United States of America, 36, 48, 10.1073/pnas.36.1.48 N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 129–140 T. Roughgarden, Stackelberg scheduling strategies, in: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 104–113 Schuurman, 2007, Performance guarantees of local search for multiprocessor scheduling, INFORMS Journal on Computing, 19, 52, 10.1287/ijoc.1050.0152 S. Suri, C.D. Tóth, Y. Zhou, Selfish load balancing and atomic congestion games, in: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004, pp. 188–195 von Stackelberg, 1934 T. Vredeveld, Combinatorial approximation algorithms: Guaranteed versus experimental performance, Ph.D. Thesis, Technische Universiteit Eindhoven, the Netherlands, 2002