Parsimonious formulations for low-diameter clusters
Parsimonious formulations for low-diameter clusters
复制标题
低直径簇的简约公式
DOI：
10.1007/s12532-020-00175-6
复制
发表时间：
2020
影响因子：
6.3
通讯作者：
Buchanan, Austin
中科院分区：
文献类型：
--
作者：
Salemi, Hosseinali;Buchanan, Austin
在网络分析中，人们经常寻找紧密结合的集群。一个“好”的星系团的一个特性是直径小（比如说，bounded byk），这就引出了ak-俱乐部的概念。在本文中，我们提出了新的路径和切割的整数规划公式检测这些低直径的子图。他们简化，概括，和/或主导几个先前存在的配方。我们表现最好的配方只使用节点变量（与以前的配方完全不同），并通过一个指数级大类的切割式不等式施加直径最大k约束。类似切割的公式的相对简单的实现很容易优于以前的方法，可以在一两秒钟内解决数十个最大俱乐部问题的实例，而其他公式则需要数小时。此外，切割式公式更一般，因为它甚至在距离不是以跳数来测量时也适用。虽然我们在本文中只考虑k俱乐部问题，但所提出的技术也可能在紧凑解决方案是关键的其他应用中有用（例如，政治区划和野生动物保护区设计）。
In the analysis of networks, one often searches for tightly knit clusters. One property of a “good” cluster is a small diameter (say, bounded byk), which leads to the concept of ak-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-kconstraints 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 maximumk-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 thek-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).
登录
查看更多内容
影响因子：
0.8
作者：
Balabhaskar Balasundaram
通讯作者：
Balabhaskar Balasundaram
DOI：
10.1287/opre.2019.1970
发表时间：
2020-06
期刊：
Oper. Res.
影响因子：
--
作者：
J. Walteros;Austin Buchanan
通讯作者：
J. Walteros;Austin Buchanan
论SAT的复杂性
DOI：
10.1109/sffcs.1999.814618
发表时间：
1999
期刊：
40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
影响因子：
--
作者：
R. Lipton;Anastasios Viglas
通讯作者：
Anastasios Viglas
影响因子：
1.6
作者：
Moradi, Esmaeel;Balasundaram, Balabhaskar
通讯作者：
Balasundaram, Balabhaskar
DOI：
10.1287/ijoc.2019.0914
发表时间：
2020-04
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
Hamidreza Validi;Austin Buchanan
通讯作者：
Hamidreza Validi;Austin Buchanan