Linear-size formulations for connected planar graph partitioning and political districting

Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more

Maximizing resilience in large-scale social networks

Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more

Formulations of the max k-cut problem on classical and quantum computers

Recent claims on “solving” combinatorial optimization problems via quantum computers have attracted researchers to work on quantum algorithms. The max k-cut problem is a challenging combinatorial optimization problem with multiple notorious mixed integer linear optimization formulations. In this paper, we revisit the binary quadratic optimization formulation of Carlson and Nemhauser (Operations Research, 1966) and provide … Read more

Political districting to minimize cut edges

When constructing political districting plans, prominent criteria include population balance, contiguity, and compactness. The compactness of a districting plan, which is often judged by the “eyeball test,” has been quantified in many ways, e.g., Length-Width, Polsby-Popper, and Moment-of-Inertia. This paper considers the number of cut edges, which has recently gained traction in the redistricting literature … Read more

Imposing contiguity constraints in political districting models

Beginning in the 1960s, techniques from operations research began to be used to generate political districting plans. A classical example is the integer programming model of Hess et al. (Operations Research 13(6):998–1006, 1965). Due to the model’s compactness-seeking objective, it tends to generate contiguous or nearly-contiguous districts, although none of the model’s constraints explicitly impose … Read more

A Note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs”

In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more

The optimal design of low-latency virtual backbones

Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for … Read more