Abstract: In stochastic online optimization, prophet inequalities under matroid constraints have been studied extensively. The philosopher benchmark(optimal online strategy) is weaker than the prophet benchmark, but it is still not fully understood how well one can compete against the optimal online strategy using polynomial computational power. Pashkovich and Dehaan showed that it is impossible to design a PTAS for computing optimal online strategy in graphic matroids.
In this talk we consider a special class of matroid constraints so called laminar matroids. There are (n) items arriving in a known order, and each item has a probability distribution over its realized value. We are also given a collection of bins on these items, where each bin (B) has a capacity (c(B)). The bins form a laminar family. When an item arrives, its value is revealed, and the algorithm must immediately decide whether to accept or reject it, while respecting all laminar capacity constraints. The goal is to maximize the expected gain of the total value of the accepted items and compare it to the gain of the optimal online policy, rather than to the prophet.
Anari et al. designed a polynomial-time approximation scheme(PTAS) for constant-depth instances, meaning that each item belongs to only a constant number of bins. Their approach uses the fact that the optimal online policy can be formulated as a linear program(LP). We will first examine this LP in the simple case where the laminar family consists of a single bin of capacity one. In general, however, the LP has exponential size and therefore cannot be solved directly in polynomial time. The main idea is to select certain small bins inside the laminar family for which the corresponding subproblems are no longer exponentially large. On these selected parts, one can use the optimal online policy, and then combine these local policies to obtain a global approximation. It remains open whether one can design a PTAS for general laminar families. |
Friday, June 12, 2026 11:30 am
-
12:30 pm
EDT (GMT -04:00)