4 papers
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Yaonan Jin, Pinyan Lu
We study revenue maximization in the unit-demand single-buyer setting. Our main result is that \textsf{Uniform-Ironed-Virtual-Value Item Pricing} guarantees a {\em tight} -appro…
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Î…
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…
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…