Exploiting Low-Rank Structure in Max-K-Cut Problems

• URL: http://arxiv.org/abs/2602.20376v1
• Date: Mon, 23 Feb 2026 21:29:47 GMT
• Title: Exploiting Low-Rank Structure in Max-K-Cut Problems
• Authors: Ria Stevens, Fangshuo Liao, Barbara Su, Jianqiang Li, Anastasios Kyrillidis,
• Abstract summary: We propose an algorithm for maximizing complex quadratic forms over a domain of size $K$.<n>We prove that this set is guaranteed to include the exact maximizer when $K=3$ and the objective is low-rank.<n>This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut.
• Score: 13.558739762168443
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• FraPPE: Fast and Efficient Preference-based Pure Exploration [17.53646399595373]
  We propose an efficient algorithm to optimally track the existing lower bound for arbitrary preference cones.<n>We prove that our proposed PrePEx algorithm, FraPPE, achieves the optimal sample complexity.
  arXiv  Detail & Related papers  (2025-08-22T16:02:06Z)
• EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization [3.249853429482705]
  Min-max optimization arises in domains such as game theory, machine adversarial learning, etc., with gradient-based methods as a typical tool.<n>In this paper, we present an apparatus for algorithmic computing globally optimal solutions in convex-based methods.<n>Next, we introduce EXOTIC Exact,.<n>an iterative innerally optimistic Tree-based solver to (approximately) solve outerally optimistic regions based on.<n>the number of calls to the inner of the class's number of calls.
  arXiv  Detail & Related papers  (2025-08-17T19:39:19Z)
• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  We consider the problem of hierarchical clustering given auxiliary information from natural oracles.<n>We show that a splitting oracle enables algorithms to outperform standard HC approaches.<n>Our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms with improved guarantees.
  arXiv  Detail & Related papers  (2025-06-05T18:22:40Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
  This work presents the first projection-free algorithm to solve bi-level optimization problems, where the objective function depends on another optimization problem. The proposed $textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$) is shown to achieve a sample complexity of $mathcalO(epsilon-2)$ for convex objectives.
  arXiv  Detail & Related papers  (2021-10-22T11:49:15Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  We present a computable approximation type algorithm, namely the linearized proximal convex method of multipliers. Some preliminary numerical results demonstrate the performance of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-06-22T07:24:17Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  We formulate the problem of maximizing a non-linear concave function of multiple long-term objectives.<n>A policy-gradient based model-free algorithm is proposed for the problem.<n>The proposed algorithm is shown to achieve convergence to within an $epsilon$ of the global optima.
  arXiv  Detail & Related papers  (2021-05-28T22:20:54Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.