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

Wei Wang, Donghyun Kim, Matthew Tetteh, Jun Liang, Wonjun Lee

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number1650061
JournalDiscrete Mathematics, Algorithms and Applications
Issue number4
Publication statusPublished - 2016 Dec 1

Bibliographical note

Publisher Copyright:
© 2016 World Scientific Publishing Company.


  • Dominating set
  • approximation algorithm
  • homophily
  • k-core
  • social networks
  • vertex connectivity

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On cost-aware biased respondent group selection for minority opinion survey'. Together they form a unique fingerprint.

Cite this