Pairwise-Independent Contention Resolution

Anupam Gupta; Jinqiao Hu; Gregory Kehne; Roie Levin

doi:10.1007/978-3-031-59835-7_15

Pairwise-Independent Contention Resolution

Anupam Gupta, Jinqiao Hu, Gregory Kehne, Roie Levin

Computer Science

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

Abstract

We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-o_k(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [14] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.

Original language	English (US)
Title of host publication	Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings
Editors	Jens Vygen, Jarosław Byrka
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	196-209
Number of pages	14
ISBN (Print)	9783031598340
DOIs	https://doi.org/10.1007/978-3-031-59835-7_15
State	Published - 2024
Event	25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024 - Wroclaw, Poland Duration: Jul 3 2024 → Jul 5 2024

Publication series

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

Conference

Conference	25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024
Country/Territory	Poland
City	Wroclaw
Period	7/3/24 → 7/5/24

Keywords

Contention Resolution
Online Algorithms
Prophet Inequalities

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-59835-7_15

Cite this

Gupta, A., Hu, J., Kehne, G., & Levin, R. (2024). Pairwise-Independent Contention Resolution. In J. Vygen, & J. Byrka (Eds.), Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings (pp. 196-209). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14679 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-59835-7_15

Pairwise-Independent Contention Resolution. / Gupta, Anupam; Hu, Jinqiao; Kehne, Gregory et al.
Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings. ed. / Jens Vygen; Jarosław Byrka. Springer Science and Business Media Deutschland GmbH, 2024. p. 196-209 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14679 LNCS).

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

Gupta, A, Hu, J, Kehne, G & Levin, R 2024, Pairwise-Independent Contention Resolution. in J Vygen & J Byrka (eds), Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14679 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 196-209, 25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024, Wroclaw, Poland, 7/3/24. https://doi.org/10.1007/978-3-031-59835-7_15

Gupta A, Hu J, Kehne G, Levin R. Pairwise-Independent Contention Resolution. In Vygen J, Byrka J, editors, Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 196-209. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-59835-7_15

Gupta, Anupam ; Hu, Jinqiao ; Kehne, Gregory et al. / Pairwise-Independent Contention Resolution. Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings. editor / Jens Vygen ; Jarosław Byrka. Springer Science and Business Media Deutschland GmbH, 2024. pp. 196-209 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f5132b551d7f46d08041b0200a6952f1,

title = "Pairwise-Independent Contention Resolution",

abstract = "We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [14] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.",

keywords = "Contention Resolution, Online Algorithms, Prophet Inequalities",

author = "Anupam Gupta and Jinqiao Hu and Gregory Kehne and Roie Levin",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024 ; Conference date: 03-07-2024 Through 05-07-2024",

year = "2024",

doi = "10.1007/978-3-031-59835-7_15",

language = "English (US)",

isbn = "9783031598340",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "196--209",

editor = "Jens Vygen and Jaros{\l}aw Byrka",

booktitle = "Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Pairwise-Independent Contention Resolution

AU - Gupta, Anupam

AU - Hu, Jinqiao

AU - Kehne, Gregory

AU - Levin, Roie

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [14] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.

AB - We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [14] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.

KW - Contention Resolution

KW - Online Algorithms

KW - Prophet Inequalities

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

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

U2 - 10.1007/978-3-031-59835-7_15

DO - 10.1007/978-3-031-59835-7_15

M3 - Conference contribution

AN - SCOPUS:85195137327

SN - 9783031598340

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

SP - 196

EP - 209

BT - Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings

A2 - Vygen, Jens

A2 - Byrka, Jarosław

PB - Springer Science and Business Media Deutschland GmbH

T2 - 25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024

Y2 - 3 July 2024 through 5 July 2024

ER -

Pairwise-Independent Contention Resolution

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this