Algorithms and Complexities of Matching Variants in Covariate Balancing

Dorit S. Hochbaum (), Asaf Levin () and Xu Rao ()
Additional contact information
Dorit S. Hochbaum: Department of IEOR, University of California, Berkeley, Berkeley, California 94720
Asaf Levin: Faculty of Industrial Engineering and Management, The Technion, Haifa 3200003, Israel
Xu Rao: Department of IEOR, University of California, Berkeley, Berkeley, California 94720

Operations Research, 2023, vol. 71, issue 5, 1800-1814

Abstract: 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.

Keywords: Optimization; algorithms; complexity; matching; covariate balance; observational studies (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2286 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1800-1814

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().