In the online metric matching problem, $n$ servers and $n$ requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in the Euclidean metric $[0, 1]^d$, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an $O(1)$-competitive algorithm for $d \neq 2$ that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an $o(\log n)$ competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the $Ω(\log n)$ barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.

We study the framework of a dynamic decision-making scenario with resource constraints. In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action in each round upon observing a random request, leading to a reward and resource consumptions that are further associated with an unknown random external factor. While previous research has already established an $\widetilde{O}(\sqrt{T})$ worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates. We first show that an $\Omega(\sqrt{T})$ distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has a degenerate optimal solution. On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an $\widetilde{O}(1)$ regret as long as the fluid LP has a unique and non-degenerate solution. Furthermore, we prove that our algorithm maintains a near-optimal $\widetilde{O}(\sqrt{T})$ regret even in the worst cases and extend these results to the setting where the request and external factor are continuous. Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.

In today's online advertising markets, it is common for advertisers to set long-term budgets. Correspondingly, advertising platforms adopt budget control methods to ensure that advertisers' payments lie within their budgets. Most budget control methods rely on the value distributions of advertisers. However, due to the complex advertising landscape and potential privacy concerns, the platform hardly learns advertisers' true priors. Thus, it is crucial to understand how budget control auction mechanisms perform under unassured priors.

In Euclidean Uniform Facility Location, the input is a set of clients in $\mathrm{R}^{d}$ and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid $\{1,ldots\,\Delta \}^{d}$, and we focus on the high-dimensional regime, where the algorithm’s space complexity must be polynomial (and certainly not exponential) in $d \cdot \log \Delta$.We present a new algorithmic framework, based on importance sampling from the stream, for $O(1)$-approximation of the optimal cost using only poly $(d\cdot\log\Delta)$ space. This framework is easy to implement in two passes, one for sampling points and the other for estimating their contribution. Over random-order streams, we can extend this to a one-pass algorithm by using the two halves of the stream separately. Our main result, for arbitrary-order streams, computes $O(d^{1.5})$-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee $O(d\cdot\log^{2}\Delta)$-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the $O(\log\Delta)$ factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by employing a geometric hashing scheme that maps points in $\mathbb{R}^{d}$ into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly $(d)$ distinct buckets.Finally, we complement our results with a proof that every streaming 1.085-approximation algorithm requires space exponential in poly $(d \cdot log \Delta)$, even for insertion-only streams.

Common path pessimism removal (CPPR) is imperative for eliminating redundant pessimism during static timing analysis (STA). However, turning on CPPR can significantly increase the analysis runtime by$10\times $–$100\times $in large designs. Recent years have seen much research on improving the algorithmic efficiencies of CPPR, but most are architecturally constrained by either the speed–accuracy tradeoff or design-specific pruning heuristics. In this article, we introduce a novel CPPR algorithm that is provably good and practically efficient. We have evaluated our algorithm on large industrial designs and demonstrated promising performance over the current state of the art. As an example, our algorithm outperforms the baseline by$36\times $–$135\times $faster when generating the top-10K post-CPPR critical paths on a million-gate design. At the extreme, our algorithm with one core is even$4\times $–$16\times $faster than the baseline with eight cores. Our algorithm also outperforms the commercial STA engine PrimeTime up to$26.99\times $faster. By exploiting parallelism within the circuit graph, we can reduce the memory consumption of our algorithm by 30%, with only 3% runtime increase.