5 papers
Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
Yong-Jin Liu, Peicheng Xie, Chuan Yang
Condat's algorithm is an efficient dynamic-threshold method for projection onto the simplex, but its extension to weighted equality constraints and the algorithmic roles of resetti…
A Parallel Evolutionary Algorithm Framework for Graph -CUT Problems
Sihong Shao, Chuan Yang
Graph k-CUT problems include many important variants whose objectives combine cut value, volume, and cardinality terms in different ways. Most existing algorithms are designed for…
Equivalent spectral theory for fundamental graph cut problems
Sihong Shao, Chuan Yang, Dong Zhang +1
We introduce and develop equivalent spectral graph theory for several fundamental graph cut problems including maxcut, mincut, Cheeger cut, anti-Cheeger cut, dual Cheeger problem a…
Conductance Estimation in Digraphs: Submodular Transformation, Lovász Extension and Dinkelbach Iteration
Sihong Shao, Chuan Yang, Xinyang Ye
Conventional spectral digraph partitioning methods typically symmetrize the adjacency matrix, thereby transforming the directed graph partitioning problem into an undirected one, w…
Dual Cheeger Constants, Signless 1-Laplacians and Maxcut
Sihong Shao, Chuan Yang, Dong Zhang
The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem, whose optimal value is referred to the dual…