Finding Condorcet Winner Configurations on a Real Line
Date Issued
2016
Date
2016
Author(s)
LIN, PO-TING
Abstract
In this thesis, we study the problem of locating k facilities under major voting criterion when all the voters are distributed along a real line. An optimal solution to this problem is called a Condorcet winner configuration. Given a placement of k facilities, there exists a fast algorithm to verify whether it is an optimal solution or not [8]. We have found a missing in this algorithm and filled the missing. According to this algorithm and our newly research results, we propose an algorithm for finding an optimal solution. If k is a fixed value, then our algorithm runs in linear time.
Subjects
facility location problem
majority voting
optimization
algorithms
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R02922067-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):5f9261e575be08efdc721ea0eb44b1dc