On cost-aware biased respondent group selection for minority opinion survey
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, Wei | - |
dc.contributor.author | Kim, Donghyun | - |
dc.contributor.author | Tetteh, Matthew | - |
dc.contributor.author | Liang, Jun | - |
dc.contributor.author | Lee, Wonjun | - |
dc.date.accessioned | 2021-09-03T16:05:57Z | - |
dc.date.available | 2021-09-03T16:05:57Z | - |
dc.date.created | 2021-06-16 | - |
dc.date.issued | 2016-12 | - |
dc.identifier.issn | 1793-8309 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/86611 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | WORLD SCIENTIFIC PUBL CO PTE LTD | - |
dc.title | On cost-aware biased respondent group selection for minority opinion survey | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Lee, Wonjun | - |
dc.identifier.doi | 10.1142/S1793830916500610 | - |
dc.identifier.wosid | 000387992200006 | - |
dc.identifier.bibliographicCitation | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, v.8, no.4 | - |
dc.relation.isPartOf | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | - |
dc.citation.title | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | - |
dc.citation.volume | 8 | - |
dc.citation.number | 4 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.subject.keywordAuthor | Dominating set | - |
dc.subject.keywordAuthor | social networks | - |
dc.subject.keywordAuthor | approximation algorithm | - |
dc.subject.keywordAuthor | k-core | - |
dc.subject.keywordAuthor | vertex connectivity | - |
dc.subject.keywordAuthor | homophily | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.