Independent sets in hypergraphs with applications to routing via fixed paths

Noga Alon, Uri Arad, Yossi Azar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

The problem of finding a large independent set in a hyper-graph by an online algorithm is considered. We provide bounds for the best possible performance ratio of deterministic vs. randomized and non-preemptive vs. preemptive algorithms. Applying these results we prove bounds for the performance of online algorithms for routing problems via fixed paths over networks.

Original languageEnglish (US)
Title of host publicationRandomization, Approximation, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings
EditorsJose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
PublisherSpringer Verlag
Pages16-27
Number of pages12
ISBN (Print)3540663290, 9783540663294
DOIs
StatePublished - Jan 1 1999
Externally publishedYes
Event3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 - Berkeley, United States
Duration: Aug 8 1999Aug 11 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1671
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999
CountryUnited States
CityBerkeley
Period8/8/998/11/99

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Independent sets in hypergraphs with applications to routing via fixed paths'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Arad, U., & Azar, Y. (1999). Independent sets in hypergraphs with applications to routing via fixed paths. In J. D. P. Rolim, A. Sinclair, D. Hochbaum, & K. Jansen (Eds.), Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings (pp. 16-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1671). Springer Verlag. https://doi.org/10.1007/978-3-540-48413-4_3