On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
Abstract
In the disjoint path allocation problem, we consider a path of L + 1 vertices, representing the nodes in a communication network. Requests for an unbounded-time communication between pairs of vertices arrive in an online fashion and some central authority has to decide which of these calls to admit. The constraint is that each edge in the path can serve only one call and the goal is to admit as many calls as possible. Advice complexity is a recently introduced method for a fine-grained analysis of the hardness of online problems. We consider the advice complexity of disjoint path allocation, measured in the length L of the path.We show that asking for a bit of advice for every edge is necessary to be optimal and give online algorithms with advice achieving a constant competitive ratio using much less advice. Furthermore, we consider the case of using less than log log L advice bits, where we prove almost matching lower and upper bounds on the competitive ratio. In the latter case, we moreover show that randomness is as powerful as advice by designing a barely random online algorithm achieving almost the same competitive ratio. Show more
Permanent link
https://doi.org/10.3929/ethz-a-009900746Publication status
publishedJournal / series
Technical Report / ETH Zurich, Department of Computer ScienceVolume
Publisher
ETH, Department of Computer ScienceSubject
SCHEDULING + TIMETABLING (OPERATIONS RESEARCH); SPECIAL PROGRAMMING METHODS; KOMMUNIKATIONSVERWALTUNG (BETRIEBSSYSTEME); COMMUNICATIONS MANAGEMENT (OPERATING SYSTEMS); WEGPLANUNG + ZEITPLANUNG (OPERATIONS RESEARCH); SPEZIELLE PROGRAMMIERMETHODENOrganisational unit
03666 - Hromkovic, Juraj / Hromkovic, Juraj
02150 - Dep. Informatik / Dep. of Computer Science
More
Show all metadata