Monroe's method: Difference between revisions

Determining the optimal Monroe outcome is NP-hard but fixed-parameter tractable.<ref name="Procaccia Rosenschein Zohar pp. 353–362">{{cite journal | last=Procaccia | first=Ariel D. | last2=Rosenschein | first2=Jeffrey S. | last3=Zohar | first3=Aviv | title=On the complexity of achieving proportional representation | journal=Social Choice and Welfare | publisher=Springer Science and Business Media LLC | volume=30 | issue=3 | date=2007-04-19 | issn=0176-1714 | doi=10.1007/s00355-007-0235-2 | pages=353–362|url=ftp://ftp.cs.huji.ac.il/users/jeff/scw06procaccia.pdf}}</ref> There exist polynomialconstant-timefactor approximation algorithms thatfor closelythe approachproblem theof maximizing representation, but not for minimizing optimummisrepresentation.<ref name="Skowron">{{Cite journal|last=Skowron|first=Piotr Krzysztof|last2=Faliszewski|first2=Piotr|last3=Slinko|first3=Arkadii|date=2013-06-29|title=Fully Proportional Representation as Resource Allocation: Approximability Results|url=https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6881|journal=Twenty-Third International Joint Conference on Artificial Intelligence|language=en|page=357}}</ref>