Political districting to minimize cut edges
From MaRDI portal
Publication:2099493
DOI10.1007/s12532-022-00221-5OpenAlexW4224935844MaRDI QIDQ2099493
Austin Buchanan, Hamidreza Validi
Publication date: 24 November 2022
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s12532-022-00221-5
integer programmingcompactnesscontiguitybranch-and-cutperimetercut edgesGerryChainpolitical redistricting
Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items (6)
Redistricting optimization with recombination: a local search case study ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ Vertex covering with capacitated trees ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Linear-size formulations for connected planar graph partitioning and political districting ⋮ Political districting to minimize cut edges
Uses Software
Cites Work
- Fundamentals of parameterized complexity
- Orbitopal fixing
- Size-constrained graph partitioning polytopes
- Orbital branching
- Maximum flow in directed planar graphs with vertex capacities
- The geo-graph in practice: creating United States congressional districts from census blocks
- Facets of the clique partitioning polytope
- Packing and partitioning orbitopes
- Simple and improved parameterized algorithms for multiterminal cuts
- On the complexity of partitioning graphs into connected subgraphs
- A cutting plane algorithm for a clustering problem
- The planar multiterminal cut problem
- The node-deletion problem for hereditary properties is NP-complete
- Cliques and clustering: A combinatorial approach
- The node capacitated graph partitioning problem: A computational study
- Min-cut clustering
- Optimal political districting
- Cluster analysis and mathematical programming
- Pruning by isomorphism in branch-and-cut
- Small covering designs by branch-and-cut
- Exploiting orbits in symmetric ILP
- On imposing connectivity constraints in integer programs
- Thinning out Steiner trees: a node-based model for uniform edge costs
- A computational comparison of symmetry handling methods for mixed integer programs
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- A tabu search heuristic and adaptive memory procedure for political districting
- Facets of the \(k\)-partition polytope
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Partitioning a graph into balanced connected classes: formulations, separation and experiments
- Political districting to minimize cut edges
- An overview of graph covering and partitioning
- A branch-and-price algorithm for capacitated hypergraph vertex separation
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- Parsimonious formulations for low-diameter clusters
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Modified orbital branching for structured symmetry with an application to unit commitment
- The \(k\)-separator problem: polyhedra, complexity and approximation results
- Linear kernels for separating a graph into components of bounded size
- The partition problem
- Weighted Voronoi region algorithms for political districting
- Political districting: from classical models to recent approaches
- Polytopes associated with symmetry handling
- The vertex \(k\)-cut problem
- Facet-defining inequalities for the simple graph partitioning polytope
- Symmetric ILP: Coloring and small integers
- On the asymmetric representatives formulation for the vertex coloring problem
- Local search algorithms for political districting
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
- The equipartition polytope. II: Valid inequalities and facets
- An Optimization Based Heuristic for Political Districting
- Extended Formulations for Packing and Partitioning Orbitopes
- The vectorization of ITPACK 2C
- Symmetry in Integer Linear Programming
- Every Planar Map is Four Colorable
- Clique-Web Facets for Multicut Polytopes
- Decomposing Matrices into Blocks
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- The clique partitioning problem: Facets and patching facets
- Partitioning a Graph into Small Pieces with Applications to Path Transversal
- Geo-Graphs: An Efficient Model for Enforcing Contiguity and Hole Constraints in Planar Graph Partitioning
- Graph Partitioning and Graph Clustering
- Redistricting algorithms
- Automated Redistricting Simulation Using Markov Chain Monte Carlo
- Imposing Contiguity Constraints in Political Districting Models
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Imposing Connectivity Constraints in Forest Planning Models
- Total Variation Isoperimetric Profiles
- A catalog of steiner tree formulations
- Disconnecting graphs by removing vertices: a polyhedral approach
- Parameterized Algorithms
- Optimal Political Districting by Implicit Enumeration Techniques
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Political districting to minimize cut edges
