Tight approximation for the minimum bottleneck generalized matching problem

Computing and Combinatorics Conference (Cocoon)


We study a problem arising in statistical analysis called the minimum bottleneck generalized matching problem that involves breaking up a population into blocks in order to carry out generalizable statistical analyses of randomized experiments. At a high level the problem is to find a clustering of the population such that each part is at least a given size and has at least a given number of elements from each treatment class (so that the experiments are statistically significant), and that all elements within a block are as similar as possible (to improve the accuracy of the analysis). (Read more)

Related Publications

All Publications

Robust Market Equilibria with Uncertain Preferences

Riley Murray, Christian Kroer, Alex Peysakhovich, Parikshit Shah

AAAI - February 12, 2020

Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking

Zhixiang Gu, Jose Moreira, David Edelsohn, Ariful Azad

SPAA - July 1, 2020

Experimentation and Performance in Advertising: An Observational Survey of Firm Practices on Facebook

Julian Runge, Steve Geinitz, Simon Ejdemyr

Expert Systems with Applications - June 9, 2020

CLARA: Confidence of Labels and Raters

Viet-An Nguyen, Peibei Shi, Jagdish Ramakrishnan, Udi Weinsberg, Henry C. Lin, Steve Metz, Neil Chandra, Jane Jing, Dimitris Kalimeris

KDD - August 24, 2020

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy