Bounding Residence Times for Atomic Dynamic Routings

References

• [1] Busch C, Magdon-Ismail M, Mavronicolas M (2007) Universal bufferless packet switching. SIAM J. Comput. 37(4):1139–1162.Crossref, Google Scholar
• [2] Busch C, Magdon-Ismail M, Mavronicolas M, Spirakis P (2006) Direct routing: Algorithms and complexity. Algorithmica 45(1):45–68.Crossref, Google Scholar
• [3] Cao Z, Chen B, Chen X, Wang C (2017) A network game of dynamic traffic. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 695–696.Google Scholar
• [4] Cao Z, Chen B, Chen X, Wang C (2021) Atomic dynamic flow games: Adaptive vs. nonadaptive agents. Oper. Res. 69(6):1680–1695.Link, Google Scholar
• [5] Cidon I, Kutten S, Mansour Y, Peleg D (1995) Greedy packet scheduling. SIAM J. Comput. 24(1):148–157.Crossref, Google Scholar
• [6] Cominetti R, Correa J, Larré O (2015) Dynamic equilibria in fluid queueing networks. Oper. Res. 63(1):21–34.Link, Google Scholar
• [7] Cominetti R, Correa J, Olver N (2017) Long term behavior of dynamic equilibria in fluid queuing networks. Eisenbrand F, Koenemann J, eds. Integer Programming and Combinatorial Optimization (Springer, Cham, Switzerland), 161–172.Crossref, Google Scholar
• [8] Correa J, Cristi A, Oosterwijk T (2019) On the price of anarchy for flows over time. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 559–577.Google Scholar
• [9] Fleischer L, Skutella M (2007) Quickest flows over time. SIAM J. Comput. 36(6):1600–1630.Crossref, Google Scholar
• [10] Graf L, Harks T (2020) The price of anarchy for instantaneous dynamic equilibria. Chen X, Gravin N, Hoefer M, Mehta R, eds. Web and Internet Economics (Springer, Cham, Switzerland), 237–251.Crossref, Google Scholar
• [11] Hall A, Hippler S, Skutella M (2007) Multicommodity flows over time: Efficient algorithms and complexity. Theoret. Comput. Sci. 379(3):387–404.Crossref, Google Scholar
• [12] Harks T, Peis B, Schmand D, Tauer B, Koch LV (2018) Competitive packet routing with priority lists. ACM Trans. Econom. Comput. 6(1):4:1–4:26.Google Scholar
• [13] Hendrickson C, Kocur G (1981) Schedule delay and departure time decisions in a deterministic model. Transportation Sci. 15(1):62–77.Link, Google Scholar
• [14] Hoefer M, Mirrokni VS, Röglin H, Teng SH (2011) Competitive routing over time. Theoret. Comput. Sci. 412(39):5420–5432.Crossref, Google Scholar
• [15] Hoppe B, Tardos E (2000) The quickest transshipment problem. Math. Oper. Res. 25(1):36–62.Link, Google Scholar
• [16] Horni A, Nagel K, Axhausen KW (2016) The Multi-Agent Transport Simulation MATSim (Ubiquity Press, London).Crossref, Google Scholar
• [17] Koch R, Skutella M (2009) Nash equilibria and the price of anarchy for flows over time. Mavronicolas M, Papadopoulou VG, eds. Algorithmic Game Theory (Springer, Berlin), 323–334.Crossref, Google Scholar
• [18] Koch R, Skutella M (2011) Nash equilibria and the price of anarchy for flows over time. Theory Comput. Systems 49(1):71–97.Crossref, Google Scholar
• [19] Koch R, Peis B, Skutella M, Wiese A (2009) Real-time message routing and scheduling. Dinur I, Jansen K, Naor J, Rolim J, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 217–230.Crossref, Google Scholar
• [20] Leighton T (1994) Methods for message routing in parallel machines. Theoret. Comput. Sci. 128(1):31–62.Crossref, Google Scholar
• [21] Leighton FT, Maggs BM, Rao SB (1994) Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14(2):167–186.Crossref, Google Scholar
• [22] Leighton F, Maggs B, Richa A (1999) Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19(3):375–401.Crossref, Google Scholar
• [23] Macko M, Larson K, Steskal L’ (2013) Braess’s paradox for flows over time. Theory Comput. Syst. 53(1):86–106.Crossref, Google Scholar
• [24] Mansour Y, Pattshamir B (1993) Greedy packet scheduling on shortest paths. J. Algorithms 14(3):449–465.Crossref, Google Scholar
• [25] Ostrovsky R, Rabani Y (1997) Universal O(congestion + dilation + log1+ϵN) local control packet switching algorithms. Proc. 29th Annual ACM Sympos. Theory Comput. (ACM, New York), 644–653.Google Scholar
• [26] Peis B, Skutella M, Wiese A (2010) Packet routing: Complexity and algorithms. Bampis E, Jansen K, eds. Approximation and Online Algorithms (Springer, Berlin), 217–228.Crossref, Google Scholar
• [27] Rabani Y, Tardos E (1996) Distributed packet switching in arbitrary networks. Proc. 28th Annual ACM Sympos. Theory Comput. (ACM, New York), 366–375.Google Scholar
• [28] Scarsini M, Schröder M, Tomala T (2018) Dynamic atomic congestion games with seasonal flows. Oper. Res. 66(2):327–339.Link, Google Scholar
• [29] Sering L, Koch LV (2019) Nash flows over time with spillback. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 935–945.Google Scholar
• [30] Sering L, Skutella M (2018) Multi-source multi-sink Nash flows over time. Borndörfer R, Storandt S, eds. Proc. 18th Workshop Algorithmic Approaches Transportation Modelling Optim. Systems (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 12:1–12:20.Google Scholar
• [31] Srinivasan A, Teo CP (2001) A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM J. Comput. 30(6):2051–2068.Crossref, Google Scholar
• [32] Vickrey WS (1969) Congestion theory and transport investment. Amer. Econom. Rev. 59(2):251–260.Google Scholar
• [33] Werth T, Holzhauser M, Krumke S (2014) Atomic routing in a deterministic queuing model. Oper. Res. Perspect. 1(1):18–41.Crossref, Google Scholar