Complexity analysis reveals tractability boundaries for covariate fine balance variants, suggesting feasible network flow solutions for observational matching.
We study here several variants of the covariates fine balance problem where we generalize some of these problems and introduce a number of others. We present here a comprehensive complexity study of the covariates 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.
No takes yet. Share an insight, caveat, or question.
Hochbaum et al. (2020) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: