More Like this

1. Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree

   https://doi.org/10.1002/rsa.21149  

   El Alaoui, Ahmed; Montanari, Andrea; Sellke, Mark (May 2023, Random Structures & Algorithms)

   Abstract Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth , we develop a local message passing algorithm whose complexity is , and that achieves near optimal cut values among all ‐local algorithms. Focusing on max‐cut, the algorithm constructs a cut of value , where is the value of the Parisi formula from spin glass theory, and (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes after removing a small fraction of vertices. Earlier work established that, for random ‐regular graphs, the typical max‐cut value is . Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max‐cut, and nearly maximum min‐bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near‐Ramanujan property of random regular graphs. 

   more » « less
2. Max cut and semidefinite rank

   https://doi.org/10.1016/j.orl.2024.107067  

   Mirka, Renee; Williamson, David P (March 2024, Operations Research Letters)

   This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n-1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs. 

   more » « less
3. Separating MAX 2-AND, MAX DI-CUT and MAX CUT

   https://doi.org/10.1109/FOCS57990.2023.00023  

   Brakensiek, Joshua; Huang, Neng; Potechin, Aaron; Zwick, Uri (November 2023, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS))

   Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is αCUT ≃ 0.87856, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UGC-hardness result for it, showing that 0.87446 ≤ αDI-CUT ≤ 0.87461, where αDI-CUT is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form z1∧z2, where z1 and z2 are literals, i.e., variables or their negations (In MAX DI-CUT each constraint is of the form \neg{x1}∧x2, where x1 and x2 are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that α2AND < 0.87435 and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND, showing that 0.87414 ≤ α2AND ≤ 0.87435. Our upper bound on MAX DI-CUT is achieved via a simple, analytical proof. The lower bounds on MAX DI-CUT and MAX 2-AND (the new approximation algorithms) use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs. 

   more » « less
4. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

   Bhojanapalli, Srinadh; Boumal, Nicolas; Jain, Prateek; Netrapalli, Praneeth (January 2018, Proceedings of the 31st Conference On Learning Theory, PMLR)

   Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer–Monteiro factorization approach for solving SDPs. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate global optima for the penalty formulation of appropriately rank-constrained SDPs, as long as the number of constraints scales sub-quadratically with the desired rank. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion. 

   more » « less
5. Optimal Bounds for the k -cut Problem

   https://doi.org/10.1145/3478018  

   Gupta, Anupam; Harris, David G.; Lee, Euiwoong; Li, Jason (February 2022, Journal of the ACM)

   In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight α λ k with probability Ω k ( n - α k ), where λ k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute λ k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λ k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process. 

   more » « less