Abstract:
Observational study is proposed to deal with the independent variables that are not under the control of the researchers. The problem we consider here is: there is one experiment group E and two disjoint controls groups C_1 and C_2. These control groups are also disjoint from E. And there is a nonnegative weight between every pair of elements of distinct groups. The goal is to find a cover of E and subsets of C_1 and C_2 through matching such that each match consists of one element of the experiment group E, k_1 elements of the first control group C_1 and k_2 elements of the second control group C_2, maximizing the total similarity where k_1 and k_2 are two parameters of the problem.
In this research, we first prove that the problem is as least as hard as to approximate the densest k-subgraph problem for k_1 = k_2 = k for large constant k. Then, we develop several approximation algorithms with good approximation ratios for k_1 = k_2 = 1 based on combinatorial methods.