We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.
Zhicheng Du, Pinyan Lu, Keyu Wang, Zihe Wang, Xiang Yan, Chunxue Yang
Online large language model (LLM) services face a pricing cold start: providers initially lack the historical data and user information needed for precise pricing, while users' willingness to pay evolves with repeated use. We formulate this challenge as a \emph{two-sided learning} problem between a provider and a user. The user learns from private usage experience, whereas the provider incurs a serving cost and dynamically adapts prices using only purchase decisions to maximize cumulative profit. The provider's central challenge is to learn to price against an evolving willingness to pay without observing the private experiences driving that evolution. We establish matching upper and lower bounds on the minimax regret over horizon $T$, identifying two cost-dependent regimes. When serving costs are sufficiently low, our Calibration-and-Tracking (CAT) algorithm achieves the optimal rate $Θ(T^{1/3})$. In the higher-cost regime, where the provider must learn whether continued service is profitable, Calibration-and-Tracking with Retirement (CAT-R) attains the optimal rate $Θ(\sqrt{T})$. This phase transition shows that serving costs affect not only profit margins but also the fundamental difficulty of learning to price LLM services. Simulations support the predicted regret scaling and show that our algorithms outperform standard online learning baselines in the evaluated settings.