Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Asher Walkover

dblp:57/4991 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
0since 2021 · last 2011
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Algorithmic game theory and mechanism design · 67% Computational complexity · 33%

Topics — the 3 heaviest of 3, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Algorithmic game theory and mechanism design › congestion games
braess's paradox
0.112005
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability · ICALP 2005
Computational complexity
hardness of approximation
0.112005
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability · ICALP 2005
Algorithmic game theory and mechanism design
network games
0.112005
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability · ICALP 2005
YearPublicationVenuePosition
2011 Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing
abstract
We give several new upper and lower bounds on the worst-case severity of Braess's paradox and the price of anarchy of selfish routing with respect to the maximum latency objective. In single-commodity networks with arbitrary continuous and nondecreasing latency functions, we prove that this worst-case price of anarchy is exactly $n-1$, where n is the number of network vertices. For Braess's paradox in such networks, we prove that removing at most c edges from a network decreases the common latency incurred by traffic at equilibrium by at most a factor of $c+1$. In particular, the worst-case severity of Braess's paradox with a single edge removal is maximized in Braess's original four-vertex network. In multicommodity networks, we exhibit an infinite family of two-commodity networks, related to the Fibonacci numbers, in which both the worst-case severity of Braess's paradox and the price of anarchy for the maximum latency objective grow exponentially with the network size. This construction demonstrates that numerous known selfish routing results for single-commodity networks have no analogues in networks with two or more commodities. We also prove an upper bound on both of these quantities that is exponential in the network size and independent of the network latency functions, showing that our construction is close to optimal. Finally, we use our family of two-commodity networks to exhibit a natural network design problem with intrinsically exponential (in)approximability.
Timothy Roughgarden, Éva Tardos, Asher Walkover
SIAM J. Discret. Math.4
2005 Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability
Timothy Roughgarden, Éva Tardos, Asher Walkover
ICALP4