In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent’s valuation, while the actual realization of the valuation is revealed only upon her arrival. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal 0.5-competitive algorithm for XOS agents. An emerging line of work focuses on designing approximation algorithms against the (computationally unbounded) optimal online algorithm. The primary goal is to design algorithms with approximation ratios strictly greater than 0.5, surpassing the impossibility result against the offline optimum. Positive results are established for unit-demand agents (Papadimitriou, Pollner, Saberi, Wajc, MOR 2024), and for \(k\)-demand agents (Braun, Kesselheim, Pollner, Saberi, EC 2024).

In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes to maximize the expected value of its hire, needs to make irrevocable online decisions about whether to hire the current candidate. The classical framework of evaluating a policy is to compute its worst-case competitive ratio against the optimal solution in hindsight, and there the best policy -- the ''1/e law'' -- has a competitive ratio of 1/e. We propose an alternative evaluation framework through the lens of regret -- the worst-case additive difference between the optimal hindsight solution and the expected performance of the policy, assuming that each value is normalized between 0 and 1. The 1/e law for the classical framework has a regret of 1 - 1/e ≈ 0.632; by contrast, we show that the class of ''pricing curves'' algorithms can guarantee a regret of at most 1/4 = 0.25 (which is tight within the class), and the class of ''best-only pricing curves'' algorithms can guarantee a regret of at most 0.190 (with a lower bound of 0.171). In addition, we show that in general, no policy can give a regret guarantee better than 0.152. Finally, we discuss other objectives in our regret-minimization framework.

We present a 0.659-competitive Quadratic Ranking algorithm for the Oblivious Bipartite Matching problem, a distribution-free version of Query-Commit Matching. This result breaks the $1-\frac{1}{e}$ barrier, addressing an open question raised by Tang, Wu, and Zhang (JACM 2023). Moreover, the competitive ratio of this distribution-free algorithm improves the best existing 0.641 ratio for Query-Commit Matching achieved by the distribution-dependent algorithm of Chen, Huang, Li, and Tang (SODA 2025). Quadratic Ranking is a novel variant of the classic Ranking algorithm. We parameterize the algorithm with two functions, and let two key expressions in the definition and analysis of the algorithm be quadratic forms of the two functions. We show that the quadratic forms are the unique choices that satisfy a set of natural properties. Further, they allow us to optimize the choice of the two functions using powerful quadratic programming solvers.

We initiate the study of Stochastic Online Correlated Selection (SOCS), a family of online rounding algorithms for the general Non-IID model of Stochastic Online Submodular Welfare Maximization and its special cases such as Online Stochastic Matching, Stochastic Ad-Words, and Stochastic Display Ads. At each time step, the algorithm sees the type of an online item and a fractional allocation of the item, then immediately allocates the item to an agent. We propose a metric called the convergence rate that measures the quality of SOCS algorithms in the above special cases. This is cleaner than most metrics in the related Online Correlated Selection (OCS) literature and may be of independent interest. We propose a Type Decomposition framework that reduces the design of SOCS algorithms to the easier special case of two-way SOCS. First, we sample a surrogate type whose fractional allocation is half-integer. The rounding is trivial for a one-way surrogate type fully allocated to one agent. For a two-way surrogate type split equally between two agents, we round it using a two-way SOCS. We design the distribution of surrogate types to get two-way types as often as possible, while respecting the original fractional allocation in expectation. Following this framework, we make progress on nu-merous problems including two open questions related to AdWords.

We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed length period of $T$. The objective is to minimize the number of machine rents. This problem generalizes the Online Machine Minimization problem where machines can be rented for an infinite period, and both problems have an asymptotically optimal competitive ratio of $O(\log(p_{\max}/p_{\min}))$ for general processing times, where $p_{\max}$ and $p_{\min}$ are the maximum and minimum processing times respectively. However, for small values of $p_{\max}/p_{\min}$, a better competitive ratio can be achieved by assuming unit-size jobs. Under this assumption, Devanur et al. (2014) gave an optimal $e$-competitive algorithm for Online Machine Minimization, and Chen and Zhang (2022) gave a $(3e+7)\approx 15.16$-competitive algorithm for Online Rent Minimization. In this paper, we significantly improve the competitive ratio of the Online Rent Minimization problem under unit size to $6$, by using a clean oracle-based online algorithm framework.

We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of googol, as well as its multiple combinatorial extensions such as $(J, K)$-secretary, 2-sided game of googol, ordinal-competitive matroid secretary. A natural approach to these tasks is to use ordinal online algorithms that at each step only consider relative ranking among the arrived elements, without looking at the numerical values of the input. We formally study the question of how cardinal algorithms (that can use numerical values of the input) can improve upon ordinal algorithms. We give first a universal construction of the input distribution for any ordinal online problem, such that the advantage of any cardinal algorithm over the ordinal algorithms is at most $1+\varepsilon$ for arbitrary small $\varepsilon\gt 0$. This implies that lower bounds from [Buchbinder, Jain, Singh, MOR 2014], [Nuti and Vondrák, SODA 2023] hold not only against any ordinal algorithm, but also against any online algorithm. Another immediate corollary is that cardinal algorithms are no better than ordinal algorithms in the matroid secretary problem with ordinal-competitive objective of [Soto, Turkieltaub, Verdugo, MOR 2021]. However, the value range of the input elements in our construction is huge: $N=$ $O\left(\frac{n^{3} \cdot n ! \cdot n !}{\varepsilon}\right) \uparrow \uparrow(n-1)$ (tower of exponents) for an input sequence of length n. As a second result, we identify a class of natural ordinal problems and find cardinal algorithm with a matching advantage of $1+\Omega\left(\frac{1}{\log (c) N}\right)$, where $\log^{(c)} N=\log \log \ldots \log N$ with c iterative logs and c is an arbitrary constant $c \leq n-2$. This suggests that for relatively small input numerical values N the cardinal algorithms may be significantly better than the ordinal algorithms on the ordinal tasks, which are typically assumed to be almost indistinguishable prior to our work. This observation leads to a natural complexity measure (we dub it cardinal complexity) for any given ordinal online task: the minimum size $N(\varepsilon)$ of different numerical values in the input such the advantage of cardinal over ordinal algorithms is at most $1+\varepsilon$ for any given $\varepsilon\gt 0$. As a third result, we show that the game of googol has much lower cardinal complexity of $N=O\left(\left(\frac{n}{\varepsilon}\right)^{n}\right)$.