We investigate prophet inequalities with competitive ratios approaching 1, seeking to generalize k-uniform matroids. We first show that large girth does not suffice: for all k, there exists a matroid of girth ≥ k and a prophet inequality instance on that matroid whose optimal competitive ratio is 1/2. Next, we show k-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio 1-O(√{(log k)/k}) for any k-fold matroid union. Our prophet inequality follows from an online contention resolution scheme. The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone 1-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a 1-Lipschitz function that is not (approximately) self-bounding.

We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC’21). Here, nodes on one side of the graph are given upfront, while at each time t, an online node and its edge weights are drawn from a time-dependent distribution. The optimal algorithm is PSPACE-hard to approximate within some universal constant. We refer to this optimal algorithm, which requires time to think (compute), as a philosopher, and refer to polynomial-time online approximations of the above as philosopher inequalities. The best known philosopher inequality for online matching yields a 0.652-approximation. In contrast, the best possible prophet inequality, or approximation of the optimum offline solution, is 0.5.

We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users.

No abstract available.

We consider a model for repeated stochastic matching where compatibility is probabilistic, is realized the first time agents are matched, and persists in the future. Such a model has applications in the gig economy, kidney exchange, and mentorship matching. We ask whether adecentralized matching process can approximate the optimal online algorithm. In particular, we consider a decentralizedstable matching process where agents match with the most compatible partner who does not prefer matching with someone else, and known compatible pairs continue matching in all future rounds. We demonstrate that the above process provides a 0.316-approximation to the optimal online algorithm for matching on general graphs. We also provide a 1/7-approximation for many-to-one bipartite matching, a 1/11-approximation for capacitated matching on general graphs, and a 1/2k-approximation for forming teams of up to k agents. Our results rely on a novel coupling argument that decomposes the successful edges of the optimal online algorithm in terms of their round-by-round comparison with stable matching.

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] → ℝ, find an element of arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a binom{n}{2} query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.