Minimizing the Worst Slowdown: Offline, Online

References

• Bansal N., Harchol-Balter M. Analysis of SRPT scheduling: Investigating unfairness. Proc. ACM SIGMETRICS (2001) (ACM Press, New York) 279–290Crossref, Google Scholar
• Bansal N., Wierman A. Competitive analysis of M/GI/1 queueing policies. (2002) . Mimeo, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Bender M., Chakrabarti S., Muthukrishnan S. Flow and stretch metrics for scheduling continuous job streams. Proc. 9th ACM-SIAM Sympos. Discrete Algorithms (1998) (SIAM Press, Philadelphia, PA) 270–279Google Scholar
• Chun Y. Consistency and monotonicity in sequencing problems. (2004) . Mimeo, Seoul National University, Seoul, South KoreaGoogle Scholar
• Demers A., Keshav S., Shenker S. Analysis and simulation of a fair queuing algorithm. Internetworking: Res. Experience (1990) 1:3–26Google Scholar
• Demko S., Hill T. Equitable distribution of indivisible objects. Math. Soc. Sci. (1988) 16(2):145–158Crossref, Google Scholar
• Dubins L. F. Group decision devices. Amer. Math Monthly (1977) 84(May):350–356Crossref, Google Scholar
• Friedman E. J., Henderson S. G. Fairness and efficiency in Web server protocols. Proc. 2003 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (2003) (ACM Press, New York) 229–237Crossref, Google Scholar
• Friedman E. J., Henderson S. G., Hurley G. Minimizing mean response time subject to fairness. (2004) . Mimeo, Cornell University, Ithaca, NYGoogle Scholar
• Harchol-Balter M., Bansal N., Schroeder B., Agrawal M. Size-based scheduling to improve Web performance. (2001) . Mimeo, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Maniquet F. A characterization of the Shapley value in queueing problems. J. Econom. Theory (2003) 109(1):90–103Crossref, Google Scholar
• Mitra M. Mechanism design in queueing problems. Econom. Theory (2001) 17:277–305Crossref, Google Scholar
• Moulin H. Uniform externalities: Two axioms for fair allocation. J. Public Econom. (1990) 43(3):305–326Crossref, Google Scholar
• Moulin H. Welfare bounds in the fair division problem. J. Econom. Theory (1991) 54(2):321–337Crossref, Google Scholar
• Moulin H. Welfare bounds in the cooperative production problem. Games Econom. Behav. (1992) 4:373–401Crossref, Google Scholar
• Moulin H. Proportional scheduling, split-proofness and merge-proofness. (2004) . Mimeo, Rice University, Houston, TXGoogle Scholar
• Queyranne M. Structure of a simple scheduling polyhedron. Math. Programming (1993) 58:263–285Crossref, Google Scholar
• Shapley L. Core of convex games. Internat. J. Game Theory (1971) 1:11–26Crossref, Google Scholar
• Smith W. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3:59–66Crossref, Google Scholar
• Sprumont Y. Ordinal cost sharing. J. Econom. Theory (1998) 81:126–162Crossref, Google Scholar
• Suijs J. On incentive compatibility and budget balancedness in public decision making. Econom. Design (1996) 2:193–209Crossref, Google Scholar
• Thomson W., Varian H., Hurwicz L., Schmeidler D., Sonnenschein H. Theories of justice based on symmetry. Social Goals and Social Organizations (1985) (Cambridge University Press, Cambridge, UK) 107–129Google Scholar
• Wierman A., Harchol-Balter M. Bounds on a fair policy with near optimal performance. (2003a) . Mimeo, Computer Science Department, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Wierman A., Harchol-Balter M. Classifying scheduling policies with respect to unfairness in an M/GI/1. Proc. ACM SIGMETRICS Conf. Measurement Model. Comput. Systems (2003b) Crossref, Google Scholar
• Wolff R. W.Stochastic Modeling and the Theory of Queues (1989) (Prentice-Hall, Englewood Cliffs, NJ) Prentice-Hall Series in Industrial and Systems EngineeringGoogle Scholar
• Wolsey L. A. Mixed integer programming formulations for production planning and scheduling problems. 12th Internat. Sympos. Math. Programming (1985) (SIAM Press, Philadelphia, PA) Google Scholar