TY - GEN
T1 - An Improved Lower Bound for Matroid Intersection Prophet Inequalities
AU - Saxena, Raghuvansh R.
AU - Velusamy, Santhoshini
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© Raghuvansh R. Saxena, Santhoshini Velusamy, and S. Matthew Weinberg; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - We consider prophet inequalities subject to feasibility constraints that are the intersection of q matroids. The best-known algorithms achieve a Θ(q)-approximation, even when restricted to instances that are the intersection of q partition matroids, and with i.i.d. Bernoulli random variables [13, 22, 2]. The previous best-known lower bound is Θ(√q) due to a simple construction of [28] (which uses i.i.d. Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of q1/2+Ω(1/log log q) by writing the construction of [28] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with pp disjoint cliques of size p, using recent techniques developed in [5].
AB - We consider prophet inequalities subject to feasibility constraints that are the intersection of q matroids. The best-known algorithms achieve a Θ(q)-approximation, even when restricted to instances that are the intersection of q partition matroids, and with i.i.d. Bernoulli random variables [13, 22, 2]. The previous best-known lower bound is Θ(√q) due to a simple construction of [28] (which uses i.i.d. Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of q1/2+Ω(1/log log q) by writing the construction of [28] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with pp disjoint cliques of size p, using recent techniques developed in [5].
KW - Intersection of Matroids
KW - Prophet Inequalities
UR - http://www.scopus.com/inward/record.url?scp=85147543081&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147543081&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.95
DO - 10.4230/LIPIcs.ITCS.2023.95
M3 - Conference contribution
AN - SCOPUS:85147543081
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Y2 - 10 January 2023 through 13 January 2023
ER -