Fast, Fair, and Efficient Flows in Networks

References

• Aronson J. E. A survey of dynamic network flows. Ann. Oper. Res. (1989) 20:1–66Crossref, Google Scholar
• Beccaria G., Bolelli A., Olaussen L., Helli E. Modelling and assessment of dynamic route guidance: The MARGOT project. Proc. 3rd IEEE Vehicle Navigation and Inform. Systems Conf. (1992) Oslo, Norway:117–126Crossref, Google Scholar
• Beckmann M. J., McGuire C. B., Winsten C. B.Studies in the Economics of Transportation (1956) (Yale University Press, New Haven, CT) Google Scholar
• Braess D. Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung (1968) 12:258–268An English translation appeared in Transportation Sci. 39 446–450, 2005Crossref, Google Scholar
• Chakrabarty D., Mehta A., Nagarajan V., Vazirani V., Riedl J., Kearns M. J., Reiter M. K. Fairness and optimality in congestion games. Proc. 6th ACM Conf. Electronic Commerce (EC) (2005) Vancouver, BC, Canada:52–57Crossref, Google Scholar
• Correa J. R., Schulz A. S., Stier-Moses N. E., Bienstock D., Nemhauser G. Computational complexity, fairness, and the price of anarchy of the maximum latency problem. Proc. 10th Internat. Integer Programming and Combin. Optim. Conf.(IPCO), New York. Lecture Notes in Comput. Sci. (2004a) 3064(Springer, Heidelberg, Germany) 59–73Crossref, Google Scholar
• Correa J. R., Schulz A. S., Stier-Moses N. E. Selfish routing in capacitated networks. Math. Oper. Res. (2004b) 29(4):961–976Link, Google Scholar
• Correa J. R., Schulz A. S., Stier-Moses N. E., Jünger M., Kaibel V. On the inefficiency of equilibria in congestion games. Proc. 11th Internat. Integer Programming and Combin. Optim. Conf. (IPCO), Berlin, Germany. Lecture Notes in Computer Science (2005) 3509(Springer, Heidelberg, Germany) 167–181Crossref, Google Scholar
• Czumaj A., Leung J. Selfish routing on the Internet. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall/CRC Computer and Information Science Series (2004) 1(CRC Press, Boca Raton, FL) . chapter 42Google Scholar
• Czumaj A., Vöcking B. Tight bounds for worst-case equilibria. Proc. 13th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (2002) San Francisco, CA(SIAM, Philadelphia, PA) 413–420Google Scholar
• Czumaj A., Krysta P., Vöcking B. Selfish traffic allocation for server farms. Proc. 34th Annual ACM Sympos. Theory of Comput. (STOC) (2002) Montreal, Canada(ACM Press, New York) 287–296Crossref, Google Scholar
• Dafermos S. C., Sparrow F. T. The traffic assignment problem for a general network. J. Res. U.S. National Bureau of Standards (1969) 73B:91–118Crossref, Google Scholar
• Fleischer L., Skutella M. Quickest flows over time. SIAM J. Comput. (2007) 36(6):1600–1630Crossref, Google Scholar
• Ford L. R., Fulkerson D. R. Constructing maximal dynamic flows from static flows. Oper. Res. (1958) 6:419–433Link, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1993) (Springer, Berlin, Germany) Crossref, Google Scholar
• Hoppe B., Tardos É. Polynomial time algorithms for some evacuation problems. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (1994) Arlington, VA(SIAM, Philadelphia, PA) 433–441Google Scholar
• Jahn O., Möhring R. H., Schulz A. S., Stier-Moses N. E. System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. (2005) 53(4):600–616Link, Google Scholar
• Jarvis J. J., Ratliff H. D. Some equivalent objectives for dynamic network flow problems. Management Sci. (1982) 28(1):106–109Link, Google Scholar
• Köhler E., Skutella M. Flows over time with load-dependent transit times. SIAM J. Optim. (2005) 15(4):1185–1202Crossref, Google Scholar
• Koutsoupias E., Papadimitriou C. H., Meinel C., Tison S. Worst-case equilibria. Proc. 16th Annual Sympos. Theoret. Aspects Comput. Sci. (STACS), Trier, Germany. Lecture Notes in Computer Science (1999) 1563(Springer, Heidelberg, Germany) 404–413Crossref, Google Scholar
• Koutsoupias E., Mavronicolas M., Spirakis P. Approximate equilibria and ball fusion. Theory Comput. Systems (2003) 36(6):683–693Crossref, Google Scholar
• Lin H., Roughgarden T., Tardos É., Walkover A., Caires L., Italiano G. F., Monteiro L., Palamidessi C., Yung M. Braess’s paradox, Fibonacci numbers, and exponential inapproximability. Automata, Languages and Programming: Proc. 32nd Internat. Colloquium (ICALP), Lisboa, Portugal. Lecture Notes in Computer Science (2005) 3580(Springer, Heidelberg, Germany) 497–512Crossref, Google Scholar
• Mavronicolas M., Spirakis P. The price of selfish routing. Proc. 33rd Annual ACM Sympos. Theory Comput. (STOC) (2001) Hersonissos, Greece(ACM Press, New York) 510–519Crossref, Google Scholar
• Papadimitriou C. H. Algorithms, games, and the Internet. Proc. 33rd Annual ACM Sympos. Theory Comput. (STOC) (2001) Hersonissos, Greece(ACM Press, New York) 749–753Crossref, Google Scholar
• Potra F., Ye Y. A quadratically convergent polynomial algorithm for solving entropy optimization problems. SIAM J. Optim. (1993) 3(4):843–860Crossref, Google Scholar
• Powell W. B., Jaillet P., Odoni A., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Stochastic and dynamic networks and routing. Networks. Handbooks in Operations Research and Management Science (1995) 4(Elsevier Science, Amsterdam, The Netherlands) 141–295Google Scholar
• Qiu L., Yang Y. R., Zhang Y., Shenker S. On selfish routing in Internet-like environments. IEEE/ACM Trans. Netw. (2006) 14(4):725–738Crossref, Google Scholar
• Roughgarden T. How unfair is optimal routing? Proc. 13th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (2002) San Francisco, CA(SIAM, Philadelphia, PA) 203–204Google Scholar
• Roughgarden T. Personal communication. (2003a) Google Scholar
• Roughgarden T. The price of anarchy is independent of the network topology. J. Comput. System Sci. (2003b) 67:341–364Crossref, Google Scholar
• Roughgarden T. The maximum latency of selfish routing. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (2004) New Orleans, LA(SIAM, Philadelphia, PA) 973–974Google Scholar
• Roughgarden T., Tardos É. How bad is selfish routing? J. ACM (2002) 49:236–259Crossref, Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1998) (J. Wiley & Sons, New York) Google Scholar
• Schulz A. S., Stier-Moses N. E. On the performance of user equilibria in traffic networks. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (2003) Baltimore, MD(SIAM, Philadelphia, PA) 86–87Google Scholar
• Vavasis S. A.Nonlinear Optimization: Complexity Issues (1991) (Oxford University Press, New York) Google Scholar
• Wardrop J. G. Some theoretical aspects of road traffic research. Proc. Institution Civil Engineers, Part II (1952) 1:325–378Crossref, Google Scholar
• Weitz D. The price of anarchy. (2001) . Unpublished manuscript, University of California, Berkeley, CAGoogle Scholar