Coordination mechanisms for selfish scheduling
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