A polytime preprocess algorithm for the maximum independent set problem

The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that … Read more

Strengthened MIP Formulations for the Liver Region Redesign Models of Akshat et al.

Liver transplantation has been a critical issue in the U.S. healthcare system for decades, and the region redesign aims to ameliorate this issue. This paper revisits two mixed integer programming (MIP) formulations of the liver region redesign problem proposed by Akshat et al. We study their first formulation considering two different modeling approaches: one compact … Read more

The set partitioning problem in a quantum context

The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more

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

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