Name
Abstract | ||
|---|---|---|
Braess's paradox states that removing a part of a network may improve the players' latency at equilibrium. In this work, we study the approximability of the best subnetwork problem for the class of random $${\\mathcal {G}}_{n,p}$$Gn,p instances proven prone to Braess's paradox by Valiant and Roughgarden RSA '10 (Random Struct Algorithms 37(4):495---515, 2010), Chung and Young WINE '10 (LNCS 6484:194---208, 2010) and Chung et al. RSA '12 (Random Struct Algorithms 41(4):451---468, 2012). Our main contribution is a polynomial-time approximation-preserving reduction of the best subnetwork problem for such instances to the corresponding problem in a simplified network where all neighbors of source s and destination t are directly connected by 0 latency edges. Building on this, we consider two cases, either when the total rate r is sufficiently low, or, when r is sufficiently high. In the first case of low$$r= O(n_{+})$$r=O(n+), here $$n_{+}$$n+ is the maximum degree of $$\\{s, t\\}$${s,t}, we obtain an approximation scheme that for any constant $$\\varepsilon 0$$ź0 and with high probability, computes a subnetwork and an $$\\varepsilon $$ź-Nash flow with maximum latency at most $$(1+\\varepsilon )L^*+ \\varepsilon $$(1+ź)Lź+ź, where $$L^*$$Lź is the equilibrium latency of the best subnetwork. Our approximation scheme runs in polynomial time if the random network has average degree $$O(\\mathrm {poly}(\\ln n))$$O(poly(lnn)) and the traffic rate is $$O(\\mathrm {poly}(\\ln \\ln n))$$O(poly(lnlnn)), and in quasipolynomial time for average degrees up to o(n) and traffic rates of $$O(\\mathrm {poly}(\\ln n))$$O(poly(lnn)). Finally, in the second case of high$$r= {\\varOmega }(n_{+})$$r=Ω(n+), we compute in strongly polynomial time a subnetwork and an $$\\varepsilon $$ź-Nash flow with maximum latency at most $$(1+2\\varepsilon + o(1))L^*$$(1+2ź+o(1))Lź. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-016-0175-2 | Algorithmica |
Keywords | Field | DocType |
Algorithmic game theory,Braess’s paradox,Seflish routing,Wardrop equilibrium,Random graphs | Mathematical optimization,Combinatorics,Mathematical economics,Random graph,Latency (engineering),Algorithmic game theory,e,Time complexity,Subnetwork,Mathematics,Wardrop equilibrium | Conference |
Volume | Issue | ISSN |
78 | 3 | 0178-4617 |
Citations | PageRank | References |
1 | 0.36 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitris Fotakis | 1 | 570 | 59.07 |
| Alexis C. Kaporis | 2 | 158 | 12.94 |
| Thanasis Lianeas | 3 | 20 | 5.85 |
| Paul G. Spirakis | 4 | 2222 | 299.05 |