Algorithms and Complexities of Matching Variants in Covariate Balancing

• 成果类型: Article
• 署名作者: Hochbaum, Dorit S.; Levin, Asaf; Rao, Xu
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2286
• 发表日期: 2023
• 页码: 1800-1814
• 关键词: algorithms; complexity; matching; covariate balance; observational studies

摘要

Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parameter tractable results for problems where the number of covariates and the number of levels of each covariate are seen as a parameter.