193 citations · 209 across the 11 of their papers we have counts for
4 papers · 1 filter
Assortment Optimization Under the Multivariate MNL Model
Xin Chen, Jiachun Li, Menglong Li +2
We study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Differe…
Satisfiability of Ordering CSPs Above Average
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability…
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami +2
The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significan…
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'Donnell, Yi Wu, Yuan Zhou
We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}^d under the Hamming distance. Recall that here H is said to be an (r, cr, p…