Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872566 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
We show how to characterize the optimization versions of these four control problems as special digraph problems and binary linear programming formulations of linear size. Our digraph characterizations allow us to prove the hardness of approximations with absolute performance guarantee for optimal constructive control by deleting candidates in Copeland and by adding candidates in Llull voting schemes and the nonexistence of efficient approximation schemes for optimal constructive control by adding and deleting candidates in Copeland and Llull voting schemes. Our experimental study of running times using LP solvers shows that for a lot of practical instances even the hard control problems can be solved very efficiently.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Frank Gurski, Magnus Roos,