Independent sets in hypergraphs with applications to routing via fixed paths

Noga Alon; Uri Arad; Yossi Azar

doi:10.1007/978-3-540-48413-4_3

Independent sets in hypergraphs with applications to routing via fixed paths

Noga Alon, Uri Arad, Yossi Azar

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 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 language	English (US)
Title of host publication	Randomization, Approximation, and Combinatorial Optimization
Subtitle of host publication	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
Editors	Jose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
Publisher	Springer Verlag
Pages	16-27
Number of pages	12
ISBN (Print)	3540663290, 9783540663294
DOIs	https://doi.org/10.1007/978-3-540-48413-4_3
State	Published - 1999
Externally published	Yes
Event	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 - Berkeley, United States Duration: Aug 8 1999 → Aug 11 1999

Publication series

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

Other

Other	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
Country/Territory	United States
City	Berkeley
Period	8/8/99 → 8/11/99

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-48413-4_3

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

Alon, Noga ; Arad, Uri ; Azar, Yossi. / Independent sets in hypergraphs with applications to routing via fixed paths. 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. editor / Jose D. P. Rolim ; Alistair Sinclair ; Dorit Hochbaum ; Klaus Jansen. Springer Verlag, 1999. pp. 16-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{abe91eb42dd34395a174e98872caf42a,

title = "Independent sets in hypergraphs with applications to routing via fixed paths",

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.",

author = "Noga Alon and Uri Arad and Yossi Azar",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 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 ; Conference date: 08-08-1999 Through 11-08-1999",

year = "1999",

doi = "10.1007/978-3-540-48413-4_3",

language = "English (US)",

isbn = "3540663290",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "16--27",

editor = "Rolim, {Jose D. P.} and Alistair Sinclair and Dorit Hochbaum and Klaus Jansen",

booktitle = "Randomization, Approximation, and Combinatorial Optimization",

address = "Germany",

}

Alon, N, Arad, U & Azar, Y 1999, Independent sets in hypergraphs with applications to routing via fixed paths. in JDP 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1671, Springer Verlag, pp. 16-27, 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, Berkeley, United States, 8/8/99. https://doi.org/10.1007/978-3-540-48413-4_3

Independent sets in hypergraphs with applications to routing via fixed paths. / Alon, Noga; Arad, Uri; Azar, Yossi.
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. ed. / Jose D. P. Rolim; Alistair Sinclair; Dorit Hochbaum; Klaus Jansen. Springer Verlag, 1999. p. 16-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1671).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Independent sets in hypergraphs with applications to routing via fixed paths

AU - Alon, Noga

AU - Arad, Uri

AU - Azar, Yossi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958739386&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958739386&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-48413-4_3

DO - 10.1007/978-3-540-48413-4_3

M3 - Conference contribution

AN - SCOPUS:84958739386

SN - 3540663290

SN - 9783540663294

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 16

EP - 27

BT - Randomization, Approximation, and Combinatorial Optimization

A2 - Rolim, Jose D. P.

A2 - Sinclair, Alistair

A2 - Hochbaum, Dorit

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 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

Y2 - 8 August 1999 through 11 August 1999

ER -

Alon N, Arad U, Azar Y. Independent sets in hypergraphs with applications to routing via fixed paths. In Rolim JDP, Sinclair A, Hochbaum D, Jansen K, editors, 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. Springer Verlag. 1999. p. 16-27. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-48413-4_3

Independent sets in hypergraphs with applications to routing via fixed paths

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this