14 citations · 29 across the 15 of their papers we have counts for
4 papers · 1 filter
The Query Complexity of Uniform Pricing
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \textit{pricing query complexity} problem in Mechanism Design. The previou…
Fully Dynamic Euclidean k-Means
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad +3
We consider the Euclidean -means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of centers) subje…
Local Search for Clustering in Almost-linear Time
Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou +1
We propose the first \emph{local search} algorithm for Euclidean clustering that attains an -approximation in almost-linear time. Specifically, for Euclidean -Means, our a…
Tight Regret Bounds for Fixed-Price Bilateral Trade
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(…