Linear-time algorithms for proportional apportionment

DOI10.1007/978-3-319-13075-0_46MaRDI QIDQ2942662zbMATH OpenOpenAlexFDO

Authors Zhanpeng Cheng, David Eppstein

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2603

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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.

Recommendations

• An Algorithm for the Equipollent Resource Allocation Problem
• scientific article; zbMATH DE number 3920153
• New apportionment methods and their quota property
• How proportional is proportional representation?
• On allocating seats to parties and districts: apportionments

Cites work

• A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
• Generalized Selection and Ranking: Sorted Matrices
• scientific article; zbMATH DE number 903850 (Why is no real title available?)
• On Huntington Methods of Apportionment
• Rounding with multiplier methods: An efficient algorithm and applications in statistics
• The complexity of selection and ranking in X+Y and matrices with sorted columns

Cited in

(6)

• On the chairman assignment problem
• Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
• Webster sequences, apportionment problems, and just-in-time sequencing
• An Algorithm for the Equipollent Resource Allocation Problem
• A Simple Algorithm for Drawing Apportionment Diagrams
• Apportionment methods and the Liu-Layland problem

This page was built for publication: Linear-time algorithms for proportional apportionment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942662)