Local-Minima-Preserving Continuous Relaxation of Ising Problems
The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical…
DiagnosticEfficient Continuous Relaxations for Dense CRF
Dense conditional random fields (CRF) with Gaussian pairwise potentials have emerged as a popular framework for several computer vision applications such as stereo correspondence and semantic segmentation. By modeling lo…
Semantic SegmentationVariational InferenceNeural Nearest Neighbors Networks
Non-local methods exploiting the self-similarity of natural signals have been well studied, for example in image analysis and restoration. Existing approaches, however, rely on k-nearest neighbors (KNN) matching in a fix…
DenoisingImage DenoisingImage RestorationImage Super-Resolution+1Convergence and Energy Landscape for Cheeger Cut Clustering
Unsupervised clustering of scattered, noisy and high-dimensional data points is an important and difficult problem. Continuous relaxations of balanced cut problems yield excellent clustering results. This paper provides…
ClusteringConstrained fractional set programs and their application in local clustering and community detection
The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxa…
ClusteringCommunity Detection