Multiple voting location and single voting location on trees

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 Σ2p-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.