TY - GEN
T1 - Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids
AU - Dinev, Atanas
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2024/1
Y1 - 2024/1
N2 - We provide a simple (1-O( 1 √ k ))-selectable Online Contention Resolution Scheme for k-uniform matroids against a fixed-order adversary. If Ai and Gi denote the set of selected elements and the set of realized active elements among the first i (respectively), our algorithm selects with probability 1-1 √ k any active element i such that |Ai-1|+1 (1-1 √ k ) -E[|Gi|]+ √ k. This implies a (1-O( 1 √ k )) prophet inequality against fixed-order adversaries for k-uniform matroids that is considerably simpler than previous algorithms [2, 4, 18]. We also prove that no OCRS can be (1-( q log k k ))-selectable for k-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that selects every active element with probability 1-θ( q log k k ) [17].
AB - We provide a simple (1-O( 1 √ k ))-selectable Online Contention Resolution Scheme for k-uniform matroids against a fixed-order adversary. If Ai and Gi denote the set of selected elements and the set of realized active elements among the first i (respectively), our algorithm selects with probability 1-1 √ k any active element i such that |Ai-1|+1 (1-1 √ k ) -E[|Gi|]+ √ k. This implies a (1-O( 1 √ k )) prophet inequality against fixed-order adversaries for k-uniform matroids that is considerably simpler than previous algorithms [2, 4, 18]. We also prove that no OCRS can be (1-( q log k k ))-selectable for k-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that selects every active element with probability 1-θ( q log k k ) [17].
KW - approximation algorithms
KW - online algorithms
KW - online contention resolutions schemes
KW - prophet inequalities
UR - https://www.scopus.com/pages/publications/85184135859
UR - https://www.scopus.com/pages/publications/85184135859#tab=citedBy
U2 - 10.4230/LIPIcs.ITCS.2024.39
DO - 10.4230/LIPIcs.ITCS.2024.39
M3 - Conference contribution
AN - SCOPUS:85184135859
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
A2 - Guruswami, Venkatesan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
Y2 - 30 January 2024 through 2 February 2024
ER -