A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem

Xinxin Li (), Ting Kei Pong (), Hao Sun () and Henry Wolkowicz ()
Additional contact information
Xinxin Li: Jilin University
Ting Kei Pong: The Hong Kong Polytechnic University
Hao Sun: University of Waterloo
Henry Wolkowicz: University of Waterloo

Computational Optimization and Applications, 2021, vol. 78, issue 3, No 7, 853-891

Abstract: Abstract The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on approximate solutions uses, in increasing strength and expense: eigenvalue, semidefinite programming, SDP, and doubly nonnegative, DNN, bounding techniques. In this paper, we derive strengthened SDP and DNN relaxations, and we propose a scalable algorithmic approach for efficiently evaluating, theoretically verifiable, both upper and lower bounds. Our stronger relaxations are based on a new gangster set, and we demonstrate how facial reduction, FR, fits in well to allow for regularized relaxations. Moreover, the FR appears to be perfectly well suited for a natural splitting of variables, and thus for the application of splitting methods. Here, we adopt the strictly contractive Peaceman-Rachford splitting method, sPRSM. Further, we bring useful redundant constraints back into the subproblems, and show empirically that this accelerates sPRSM.In addition, we employ new strategies for obtaining lower bounds and upper bounds of the optimal value of MC from approximate iterates of the sPRSM thus aiding in early termination of the algorithm. We compare our approach with others in the literature on random datasets and vertex separator problems. This illustrates the efficiency and robustness of our proposed method.

Keywords: Semidefinite relaxation; Doubly nonnegative relaxation; Min-cut; Graph partitioning; Vertex separator; Peaceman-Rachford splitting method; Facial reduction; 05C70; 90C22; 90C25; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-020-00261-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:78:y:2021:i:3:d:10.1007_s10589-020-00261-4

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-020-00261-4

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().