David Eppstein

Chancellor's Professor
Department of Computer Science
UC Irvine

"Linear-time Algorithms for Proportional Apportionment"

Thursday, May 12
SSPA 2112
4:00 - 5:00 pm


The apportionment problem deals with the fair distribution of a discrete set of k indivisible resources (such as legislative seats) to n entities (such as parties or geographic subdivisions). Highest averages methods are a frequently used class of methods for solving this problem. We present an O(n)-time algorithm for performing apportionment under a large class of highest averages methods. Our algorithm works for all highest averages methods used in practice. (Joint work with Zhanpeng Cheng.)



© UC Irvine School of Social Sciences - 3151 Social Sciences Plaza, Irvine, CA 92697-5100 - 949.824.2766