Prophet Inequality of Partition Matroid Intersection

Abstract

We study the prophet inequality for intersections of $d$ partition matroids, which is generalized by the prophet inequality for $d$-dimensional and $d$-partite hypergraph matchings. The tight bound for this constraint is currently open, with the best algorithms guaranteeing $O(d)$ approximations and the best lower bound being $\omega(\sqrt{d})$, even when the valuation distributions are relaxed to be I.I.D. Bernoulli. In order to shed light on potentially bridging this gap, we study two algorithms for the setting. We first show that one algorithm designed for general downward-closed feasibility constraints achieves the $\sqrt{d}$ lower bound on a partition matroid intersection instance. We do so by adapting the original analysis that shows it achieves a $\log(n)$ approximation on general set systems. We then analyze ways to beat the greedy algorithm on the fixed $d$-dimensional and $d$-partite hypergraph maximum matching problem. We propose one approach and extend lemmas for bipartite matching, inspired from an algorithm designed for intersections of two general matroids.