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

3 Citations (Scopus)

Abstract

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
Pages77-88
Number of pages12
ISBN (Electronic)9783319156118
DOIs
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)
Volume8973
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Algorithms and Computation, WALCOM 2015
Country/TerritoryBangladesh
CityDhaka
Period2015/02/262015/02/28

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this