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 -