TY - GEN
T1 - Forming plurality at minimum cost
AU - Lin, Wei Yin
AU - Wu, Yen Wei
AU - Wang, Hung Lung
AU - Chao, Kun Mao
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84923698982&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84923698982&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-15612-5_8
DO - 10.1007/978-3-319-15612-5_8
M3 - Conference contribution
AN - SCOPUS:84923698982
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 77
EP - 88
BT - WALCOM
A2 - Rahman, M. Sohel
A2 - Tomita, Etsuji
PB - Springer Verlag
T2 - 9th International Workshop on Algorithms and Computation, WALCOM 2015
Y2 - 26 February 2015 through 28 February 2015
ER -