On cost-aware biased respondent group selection for minority opinion survey

This paper discusses a new approach to use a specially constructed social relation graph with high homophily to select a survey respondent group under a limited budget such that the result of the survey is biased to the minority opinions. This approach has a wide range of potential applications, e.g., collecting diversified complaints from the customers while most of them are satisfied, but is hardly investigated. We formulate the problem of computing such a group as the p-biased-representative selection problem (p-BRSP), where p represents the size of the group constraint by the available budget. This problem has two independent optimization goals and therefore is difficult to deal with. We introduce two polynomial time algorithms for the problem, where each of which has an approximation ratio with respect to each of the objectives when the other optimization objective is substituted with a constraint. Under the substituted constraint, we prove that the first algorithm is an O(lnδ)-approximation (which is best possible) algorithm with respect to the first objective and the second algorithm is a 2-approximation (which is best possible) with respect to the second objective, where δ is the degree of the input social relation graph.