An Improved Lower Bound for Matroid Intersection Prophet Inequalities

Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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

Original languageEnglish (US)
Title of host publication14th Innovations in Theoretical Computer Science Conference, ITCS 2023
EditorsYael Tauman Kalai
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772631
DOIs
StatePublished - Jan 1 2023
Event14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States
Duration: Jan 10 2023Jan 13 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume251
ISSN (Print)1868-8969

Conference

Conference14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/TerritoryUnited States
CityCambridge
Period1/10/231/13/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Intersection of Matroids
  • Prophet Inequalities

Fingerprint

Dive into the research topics of 'An Improved Lower Bound for Matroid Intersection Prophet Inequalities'. Together they form a unique fingerprint.

Cite this