> Detailanzeige

Barhum, Kfir [Verfasser:in]; Böckenhauer, Hans-Joachim [Verfasser:in]; Forišek, Michal [Verfasser:in]; Gebauer, Heidi [Verfasser:in]; Hromkovič, Juraj [Verfasser:in]; Krug, Sacha [Verfasser:in]; Smula, Jasmin [Verfasser:in]; Steffen, Björn [Verfasser:in]

On the Power of Advice and Randomization for the Disjoint Path Allocation Problem

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Bericht; E-Book
  • Titel: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
  • Beteiligte: Barhum, Kfir [Verfasser:in]; Böckenhauer, Hans-Joachim [Verfasser:in]; Forišek, Michal [Verfasser:in]; Gebauer, Heidi [Verfasser:in]; Hromkovič, Juraj [Verfasser:in]; Krug, Sacha [Verfasser:in]; Smula, Jasmin [Verfasser:in]; Steffen, Björn [Verfasser:in]
  • Erschienen: ETH, Department of Computer Science, 2013
  • Erschienen in: Technical Report / ETH Zurich, Department of Computer Science, 788
  • Sprache: Englisch
  • DOI: https://doi.org/20.500.11850/67932; https://doi.org/10.3929/ethz-a-009900746
  • Schlagwörter: KOMMUNIKATIONSVERWALTUNG (BETRIEBSSYSTEME) ; Data processing ; SPEZIELLE PROGRAMMIERMETHODEN ; WEGPLANUNG + ZEITPLANUNG (OPERATIONS RESEARCH) ; COMMUNICATIONS MANAGEMENT (OPERATING SYSTEMS) ; SCHEDULING + TIMETABLING (OPERATIONS RESEARCH) ; SPECIAL PROGRAMMING METHODS ; computer science
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang
  • Rechte-/Nutzungshinweise: Urheberrechtsschutz - Nicht kommerzielle Nutzung gestattet