Exploiting Low-Rank Structure in Max-K-Cut Problems
We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Riemannian Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates
Low-rank optimization problems with sparse simplex constraints involve variables that must satisfy nonnegativity, sparsity, and sum-to-one conditions, making their optimization particularly challenging due to the interpl…
Riemannian optimizationDirection-of-Arrival Estimation for Constant Modulus Signals Using a Structured Matrix Recovery Technique
This paper addresses the problem of direction-of-arrival (DOA) estimation for constant modulus (CM) source signals using a uniform or sparse linear array. Existing methods typically exploit either the Vandermonde structu…
Direction of Arrival EstimationSeveral Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors
Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems…
Tensor DecompositionFederated Low-Rank Tensor Estimation for Multimodal Image Reconstruction
Low-rank tensor estimation offers a powerful approach to addressing high-dimensional data challenges and can substantially improve solutions to ill-posed inverse problems, such as image reconstruction under noisy or unde…
Federated LearningImage ReconstructionTensor DecompositionMidRank: Learning to rank based on subsequences
We present a supervised learning to rank algorithm that effectively orders images by exploiting the structure in image sequences. Most often in the supervised learning to rank literature, ranking is approached either by …
Learning-To-Rank