2026-07-22T19:33:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17598 2024-03-06T11:00:01Z ddc:004 open_access

An Improved Lower Bound for Matroid Intersection Prophet Inequalities Saxena, Raghuvansh R. Velusamy, Santhoshini Weinberg, S. Matthew Prophet Inequalities Intersection of Matroids 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 [José R. Correa et al., 2022; Moran Feldman et al., 2016; Marek Adamczyk and Michal Wlodarczyk, 2018]. The previous best-known lower bound is Θ(√q) due to a simple construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] (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 q^{1/2+Ω(1/log log q)} by writing the construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with p^p disjoint cliques of size p, using recent techniques developed in [Noga Alon and Ryan Alweiss, 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raghuvansh R. Saxena and Santhoshini Velusamy and S. Matthew Weinberg 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.95 urn:nbn:de:0030-drops-175986 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.95 eng https://creativecommons.org/licenses/by/4.0/legalcode