A Unified Approach to Truthful Scheduling on Related Machines

References

• Alon N, Azar Y, Woeginger GJ, Yadid T (1997) Approximation schemes for scheduling. Proc. 8th Symp. Discrete Algorithms, SODA ’97 (SIAM, Philadelphia), 493–500.Google Scholar
• Alon N, Azar Y, Woeginger GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J. Scheduling 1(1):55–66.Crossref, Google Scholar
• Andelman N, Azar Y, Sorani M (2007) Truthful approximation mechanisms for scheduling selfish related machines. Theory Comput. Systems 40(4):423–436.Crossref, Google Scholar
• Archer A (2004) Mechanisms for discrete optimization with rational agents. Unpublished doctoral dissertation, Cornell University, Ithaca, NY.Google Scholar
• Archer A, Tardos É (2001) Truthful mechanisms for one-parameter agents. Proc. 42st Symp. Foundations Comput. Sci., FOCS ’01 (IEEE, Piscataway, NJ), 482–491.Crossref, Google Scholar
• Auletta V, Prisco RD, Penna P, Persiano G (2004) Deterministic truthful approximation mechanisms for scheduling related machines. Proc. 21st Internat. Sympos. Theoret. Aspects Comput. Sci. STACS ’04 (Springer, Berlin), 608–619.Crossref, Google Scholar
• Awerbuch B, Azar Y, Grove EF, Kao M-Y, Krishnan P, Vitter JS (1995) Load balancing in the lp norm. Proc. 36th Symp. Foundations Comput. Sci., FOCS ’95 (IEEE, Piscataway, NJ), 383–391.Google Scholar
• Azar Y, Epstein L (1998) Approximation schemes for covering and scheduling on related machines. Proc. 1st Internat. Workshop on Approximation Algorithms for Combinatorial Optim., APPROX ’98 (Springer, Berlin), 39–47.Crossref, Google Scholar
• Azar Y, Epstein L, Richter Y, Woeginger GJ (2004) All-norm approximation algorithms. J. Algorithms 52(2):120–133.Crossref, Google Scholar
• Bansal N, Pruhs KR (2010) Server scheduling to balance priorities, fairness, and average quality of service. SIAM J. Comput. 39(7):3311–3335.Crossref, Google Scholar
• Bansal N, Sviridenko M (2006) The Santa Claus problem. Proc. 38th Symp. Theory Comput., STOC ’06 (ACM, New York), 31–40.Crossref, Google Scholar
• Caragiannis I (2008) Better bounds for online load balancing on unrelated machines. Proc. 19th Symp. Discrete Algorithms, SODA ’08 (SIAM, Philadelphia), 972–981.Google Scholar
• Chandra AK, Wong CK (1975) Worst-case analysis of a placement algorithm related to storage allocation. SIAM J. Comput. 4(3):249–263.Crossref, Google Scholar
• Christodoulou G, Kovács A (2013) A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput. 42(4):1572–1595.Crossref, Google Scholar
• Christodoulou G, Koutsoupias E, Vidali A (2009) A lower bound for scheduling mechanisms. Algorithmica 55(4):729–740.Crossref, Google Scholar
• Christodoulou G, Kovács A, van Stee R (2013) A truthful constant approximation for maximizing the minimum load on related machines. Theoret. Comput. Sci. 489–490:88–98.Crossref, Google Scholar
• Cody RA, Coffman EG Jr (1976) Record allocation for minimizing expected retrieval costs on drum-like storage devices. J. ACM 23(1):103–115.Crossref, Google Scholar
• Dhangwatnotai P, Dobzinski S, Dughmi S, Roughgarden T (2011) Truthful approximation schemes for single-parameter agents. SIAM J. Comput. 40(3):915–933.Crossref, Google Scholar
• Efraimidis P, Spirakis PG (2006) Approximation schemes for scheduling and covering on unrelated machines. Theoret. Comput. Sci. 359(1–3):400–417.Crossref, Google Scholar
• Epstein L, Sgall J (2004) Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica 39(1):43–57.Crossref, Google Scholar
• Epstein L, van Stee R (2010) Maximizing the minimum load for selfish agents. Theoret. Comput. Sci. 411(1):44–57.Crossref, Google Scholar
• Friesen DK, Deuermeyer BL (1981) Analysis of greedy solutions for a replacement part sequencing problem. Math. Oper. Res. 6(1):74–87.Link, Google Scholar
• Gonzalez T, Ibarra OH, Sahni S (1977) Bounds for LPT schedules on uniform processors. SIAM J. Comput. 6(1):155–166.Crossref, Google Scholar
• Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45(9):1563–1581.Crossref, Google Scholar
• Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM 34(1):144–162.Crossref, Google Scholar
• Hochbaum DS, Shmoys DB (1988) A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput. 17(3):539–551.Crossref, Google Scholar
• Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2):317–327.Crossref, Google Scholar
• Kovács A (2005) Fast monotone 3-approximation algorithm for scheduling related machines. Proc. 13th Annual Eur. Sympos. Algorithms, ESA ’05 (Springer, Berlin), 616–627.Crossref, Google Scholar
• Kovács A (2009) Tighter approximation bounds for LPT scheduling in two special cases. J. Discrete Algorithms 7(3):327–340.Crossref, Google Scholar
• Lavi R, Swamy C (2009) Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. Games Econom. Behav. 67(1):99–124.Crossref, Google Scholar
• Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• Nisan N, Ronen A (2001) Algorithmic mechanism design. Games Econom. Behav. 35(1–2):166–196.Crossref, Google Scholar
• Riley JG, Samuelson WF (1981) Optimal auctions. Amer. Econom. Rev. 71(3):381–392.Google Scholar
• Woeginger GJ (1997) A polynomial time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4):149–154.Crossref, Google Scholar