Jack Zhang

Partitioning a graph into low-diameter clusters

  • Jack Zhang
  • Lucas Vinícius Silveira de Lima
  • Hamidreza Validi
  • Logan Smith
  • Austin Buchanan
  • Illya V. Hicks
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization Tags , , , ,

    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

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

  • Jack Zhang
  • Hamidreza Validi
  • Austin Buchanan
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    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