Computerized Redistricting: Examining the Weighted Points Version of the Capacitated K-Center Problem

Date
2014
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Tripod URL
Identifier
Abstract
Every ten years, when states are forced to redraw their congressional districts, the process is intensely partisan, and the outcome is rarely fair and democratic. In the last few decades, the growing capabilities of computers have offered the promise of objective, computerized redistricting. Unfortunately, the redistricting problem can be shown to be NP-Complete, but there are a number of approximation algorithms and heuristics that are effective. I focus on an approximation algorithm for the capacitated k-center problem. I revise this algorithm, so that it can be applied to the redistricting problem, and I show through experimental testing that the algorithm is effective. My results demonstrate that computers can facilitate the process by giving mapmakers access to more options.
Description
Citation
Collections