Optimization Online


Parsimonious formulations for low-diameter clusters

Hosseinali Salemi (hosseinali.salemi***at***okstate.edu)
Austin Buchanan (buchanan***at***okstate.edu)

Abstract: In the analysis of networks, one often searches for tightly knit clusters. One property of a ``good'' cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or dominate several previously existing formulations. Our best-performing formulation uses only node variables (quite unlike previous formulations) and imposes the diameter-at-most-$k$ constraints via an exponentially large class of cut-like inequalities. A relatively simple implementation of the cut-like formulation easily outperforms previous approaches, solving dozens of instances of the maximum $k$-club problem in a second or two that would take hours by other formulations. Moreover, the cut-like formulation is more general in the sense that it applies even when distances are not measured in terms of hops. While we consider only the $k$-club problem in this paper, the proposed techniques may also be useful in other applications where compact solutions are key (e.g., political districting and wildlife reserve design).

Keywords: $k$-club; low-diameter; cluster; integer programming; hop constraint; distance constraint; bounded diameter; length-bounded cut;

Category 1: Network Optimization

Category 2: Integer Programming

Category 3: Combinatorial Optimization

Citation: Submitted to a journal. Code is available at https://github.com/halisalemi/ParsimoniousKClub

Download: [PDF]

Entry Submitted: 09/11/2017
Entry Accepted: 09/11/2017
Entry Last Modified: 08/15/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society