Forming plurality at minimum cost

Wei Yin Lin, Yen Wei Wu, Hung Lung Wang, Kun Mao Chao

研究成果: 書貢獻/報告類型會議論文篇章

3 引文 斯高帕斯(Scopus)

摘要

In this paper, we are concerned with a kind of spatial equilibria, the plurality points, in two-dimensional Euclidean space. Given a set of voters, each of which corresponds to a point, a plurality point is defined as a point closer to at least as many voters as any other point in the space. We generalize the definition by appending weights on the voters, and define the plurality point as a point ∆ satisfying that the sum of weights of the voters closer to ∆ is no less than that of the voters closer to any other point in the space. To remedy the issue of the nonexistence of plurality points, we investigate the problem of eliminating some voters with minimum “cost” so that there is a plurality point with respect to the remaining voters. We show that the problem is NP-hard. Moreover, if all voters’ weights are restricted to be equal, we show that the problem can be solved in O(n5 log n) time, where n is the number of voters.

原文英語
主出版物標題WALCOM
主出版物子標題Algorithms and Computation - 9th InternationalWorkshop,WALCOM 2015, Proceedings
編輯M. Sohel Rahman, Etsuji Tomita
發行者Springer Verlag
頁面77-88
頁數12
ISBN(電子)9783319156118
DOIs
出版狀態已發佈 - 2015
對外發佈
事件9th International Workshop on Algorithms and Computation, WALCOM 2015 - Dhaka, 孟加拉国
持續時間: 2015 二月 262015 二月 28

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
8973
ISSN(列印)0302-9743
ISSN(電子)1611-3349

會議

會議9th International Workshop on Algorithms and Computation, WALCOM 2015
國家/地區孟加拉国
城市Dhaka
期間2015/02/262015/02/28

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「Forming plurality at minimum cost」主題。共同形成了獨特的指紋。

引用此