A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria
From MaRDI portal
Publication:2719123
DOI10.1137/S0097539798335596zbMath0980.68050MaRDI QIDQ2719123
No author found.
Publication date: 21 June 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
linear programmingapproximation algorithmsrandomized algorithmsrandomized roundingmulticommodity flowcovering integer programspacket routingdiscrete ham-sandwich theoremsrounding theorems
Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (7)
Local ratio method on partial set multi-cover ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Universal Packet Routing with Arbitrary Bandwidths and Transit Times ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ Time-optimum packet scheduling for many-to-one routing in wireless sensor networks ⋮ Approximation algorithms for covering/packing integer programs ⋮ Bounding Residence Times for Atomic Dynamic Routings
This page was built for publication: A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria
