Multiple voting location and single voting location on trees
| Autor: | Joachim Spoerhase, Hans-Christoph Wirth, Hartmut Noltemeier |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Anti-plurality voting
Ranked pairs Mathematical optimization Information Systems and Management Optimization problem Theoretical computer science General Computer Science media_common.quotation_subject Management Science and Operations Research Condorcet method Tree (graph theory) Industrial and Manufacturing Engineering Facility location problem Cardinal voting systems Modeling and Simulation Voting Mathematics media_common |
| Zdroj: | European Journal of Operational Research. 181:654-667 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2006.06.039 |
| Popis: | We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by γ -proportion. We show that for multiple voting location, Condorcet and Simpson decision problems are Σ 2 p -complete, and investigate the approximability of the Simpson and the Simpson score optimization problem. Further we contribute a result towards lower bounds on the complexity of the single voting location problem. On the positive side we develop algorithms for the optimization problems on tree networks which are substantially faster than the existing algorithms for general graphs. Finally we suggest a generalization of the indifference notion to threshold functions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect