Forming plurality at minimum cost

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (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.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 9th InternationalWorkshop,WALCOM 2015, Proceedings
EditorsM. Sohel Rahman, Etsuji Tomita
PublisherSpringer Verlag
Number of pages12
ISBN (Electronic)9783319156118
Publication statusPublished - 2015
Externally publishedYes
Event9th International Workshop on Algorithms and Computation, WALCOM 2015 - Dhaka, Bangladesh
Duration: 2015 Feb 262015 Feb 28

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th International Workshop on Algorithms and Computation, WALCOM 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Forming plurality at minimum cost'. Together they form a unique fingerprint.

Cite this