Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.25614 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- This paper investigates why and when the edge-based districting problem becomes computationally intractable. The overall problem is represented as an exact mathematical programming formulation consisting of an objective function and several constraint groups, each enforcing a well-known districting criterion such as balance, contiguity, or compactness. While districting is known to be NP-hard in general, we study what happens when specific constraint groups are relaxed or removed. The results identify precise boundaries between tractable subproblems (in P) and intractable ones (NP-hard). The paper also discusses implications on node-based analogs of the featured districting problems, and it considers alternative notions of certain criteria in its analysis.