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 -