[go: up one dir, main page]

Lin et al., 2011 - Google Patents

Stronger bounds on Braess's paradox and the maximum latency of selfish routing

Lin et al., 2011

View PDF
Document ID
11690272159955770434
Author
Lin H
Roughgarden T
Tardos Ă
Walkover A
Publication year
Publication venue
SIAM Journal on Discrete Mathematics

External Links

Snippet

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 …
Continue reading at www.timroughgarden.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/124—Shortest path evaluation using a combination of metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H04L12/56—Packet switching systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery

Similar Documents

Publication Publication Date Title
Lin et al. Stronger bounds on Braess's paradox and the maximum latency of selfish routing
Feillet A tutorial on column generation and branch-and-price for vehicle routing problems
Goel et al. On the communication and streaming complexity of maximum bipartite matching
Kolliopoulos et al. Approximating disjoint-path problems using packing integer programs
Letchford et al. Pricing routines for vehicle routing with time windows on road networks
WO2014052878A1 (en) System and methods for improved network routing
Avella et al. Metric inequalities and the network loading problem
Hajiaghayi et al. Local search algorithms for the red-blue median problem
Nace et al. Max–min fairness in multi-commodity flows
Harks et al. Computing pure nash and strong equilibria in bottleneck congestion games
TWI398782B (en) System reliability evaluation method for transmission by two minimal paths in time restriction
Christodoulou et al. Designing networks with good equilibria under uncertainty
Ruthmair et al. A layered graph model and an adaptive layers framework to solve delay-constrained minimum tree problems
Mattia et al. A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation
Elkin et al. Linear-size hopsets with small hopbound, and distributed routing with low memory
Chen et al. Meet and merge: Approximation algorithms for confluent flows
Van Zuylen Deterministic sampling algorithms for network design
Fotakis Congestion games with linearly independent paths: Convergence time and price of anarchy
Rachadi et al. Self avoiding paths routing algorithm in scale-free networks
Golin et al. Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
Lin et al. Braess’s paradox, Fibonacci numbers, and exponential inapproximability
Dutta et al. Embedding paths into trees: VM placement to minimize congestion
Hajiaghayi et al. Budgeted red-blue median and its generalizations
CN102710596A (en) Routing selecting method based on QoE (Quality of Experience)
Harks et al. Computing pure Nash and strong equilibria in bottleneck congestion games