On cost-aware biased respondent group selection for minority opinion survey
- Authors
- Wang, Wei; Kim, Donghyun; Tetteh, Matthew; Liang, Jun; Lee, Wonjun
- Issue Date
- Dec-2016
- Publisher
- WORLD SCIENTIFIC PUBL CO PTE LTD
- Keywords
- Dominating set; social networks; approximation algorithm; k-core; vertex connectivity; homophily
- Citation
- DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, v.8, no.4
- Journal Title
- DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
- Volume
- 8
- Number
- 4
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/86611
- DOI
- 10.1142/S1793830916500610
- ISSN
- 1793-8309
- Abstract
- 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 Delta)-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 Delta is the degree of the input social relation graph.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
![qrcode](https://api.qrserver.com/v1/create-qr-code/?size=55x55&data=https://scholar.korea.ac.kr/handle/2021.sw.korea/86611)
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.