Hamidreza Validi Given graph G = (V,E) with vertex set V and edge set E, the max k-cut problem seeks to partition the vertex set V into at most k subsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number … Read more
This paper studies the problems of partitioning the vertices of a graph G = (V,E) into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at … Read more
Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions … Read more
Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover … Read more
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
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 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
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
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
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