Optimal oblivious routing in polynomial time

DOI10.1016/J.JCSS.2004.04.010MaRDI QIDQ5917575zbMATH OpenOpenAlexFDO

Authors Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke

Publication date 18 November 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.04.010

zbMATH Keywords

Communication networksOblivious ratioOblivious routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Communication networks in operations research (90B18)

Recommendations

• Optimal oblivious routing in polynomial time
• An optimal time bound for oblivious routing
• Oblivious routing on node-capacitated and directed graphs
• Oblivious routing on node-capacitated and directed graphs
• Oblivious routing in directed graphs with random demands

Cites work

• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Online algorithms. The state of the art
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Routing, merging, and sorting on parallel models of computation
• Tight bounds for oblivious routing in the hypercube

Cited in

(25)

• Optimal oblivious routing under linear and ellipsoidal uncertainty
• Oblivious routing with limited buffer capacity
• On the approximability of robust network design
• Oblivious routing on node-capacitated and directed graphs
• Semi-oblivious routing: lower bounds
• Threshold rules for online sample selection
• Oblivious integral routing for minimizing the quadratic polynomial cost
• Tight bounds for oblivious routing in the hypercube
• Serving in the dark should be done non-uniformly
• A Time-Randomness Trade-Off for Oblivious Routing
• Oblivious routing in directed graphs with random demands
• Oblivious routing on node-capacitated and directed graphs
• Compact oblivious routing
• scientific article; zbMATH DE number 7561477 (Why is no real title available?)
• Mixing times and \(\ell_p\) bounds for oblivious routing
• Routing under balance
• Online Packet Admission and Oblivious Routing in Sensor Networks
• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• Optimal oblivious routing in polynomial time
• Affine routing for robust network design
• Optimal oblivious reconfigurable networks
• An efficient approach to optimization of semi‐stable routing in multicommodity flow networks
• hop-constrained oblivious routing
• Traffic-oblivious multi-commodity flow network design
• An optimal time bound for oblivious routing

This page was built for publication: Optimal oblivious routing in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917575)