Preprint
A $k$-medoids Approach to Exploring Districting Plans
ArXiv.org
03/10/2023
DOI: 10.48550/arxiv.2303.05631
Abstract
Researchers and legislators alike continue the search for methods of drawing
fair districting plans. A districting plan is a partition of a state's
subdivisions (e.g. counties, voting precincts, etc.). By modeling these
districting plans as graphs, they are easier to create, store, and operate on.
Since graph partitioning with balancing populations is a computationally
intractable (NP-hard) problem most attempts to solve them use heuristic
methods. In this paper, we present a variant on the $k$-medoids algorithm
where, given a set of initial medoids, we find a partition of the graph's
vertices to admit a districting plan. We first use the $k$-medoids process to
find an initial districting plan, then use local search strategies to fine-tune
the results, such as reducing population imbalances between districts. We also
experiment with coarsening the graph to work with fewer vertices. The algorithm
is tested on Iowa and Florida using 2010 census data to evaluate the
effectiveness.
Details
- Title: Subtitle
- A $k$-medoids Approach to Exploring Districting Plans
- Creators
- Jared GroveSuely OliveiraAnthony PizzimentiDavid E Stewart
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2303.05631
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 03/10/2023
- Academic Unit
- Mathematics; Computer Science
- Record Identifier
- 9984411063402771
Metrics
9 Record Views