Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
From MaRDI portal
Publication:4369893
DOI10.1145/227683.227684zbMath0885.68088OpenAlexW1985123706WikidataQ55934039 ScholiaQ55934039MaRDI QIDQ4369893
David P. Williamson, Michel X. Goemans
Publication date: 28 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/227683.227684
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions, On the directed cut cone and polytope, Bounding duality gap for separable problems with linear constraints, Numerical methods for the Genvar criterion of multiple-sets canonical analysis, Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}, Sublinear time algorithms for approximate semidefinite programming, On conic QPCCs, conic QCQPs and completely positive programs, Complexity of approximating CSP with balance/hard constraints, A dichotomy for local small-bias generators, A computational study for bilevel quadratic programs using semidefinite relaxations, A degree based approach to find Steiner trees, Sums of squares on the hypercube, Cryptographic hardness of random local functions. Survey, Generating cutting planes for the semidefinite relaxation of quadratic programs, Memetic search for the max-bisection problem, A nonmonotone GRASP, Average case polyhedral complexity of the maximum stable set problem, Approximating the little Grothendieck problem over the orthogonal and unitary groups, An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding, A computational study and survey of methods for the single-row facility layout problem, Solution of sectorization problems for an air traffic management area. II: Development of sectorization algorithms, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Semidefinite relaxations of ordering problems, A homotopy method for nonlinear semidefinite programming, Flow metrics, New semidefinite programming relaxations for box constrained quadratic program, Stochastic nuclear outages semidefinite relaxations, Semidefinite relaxations for non-convex quadratic mixed-integer programming, Reoptimization of constraint satisfaction problems with approximation resistant predicates, Randomized projective methods for the construction of binary sparse vector representations, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Approximation algorithms for discrete polynomial optimization, An improved lower bound and approximation algorithm for binary constrained quadratic programming problem, Optimal detection of sparse principal components in high dimension, Small bipartite subgraph polytopes, Separator-based data reduction for signed graph balancing, Approximation with a fixed number of solutions of some multiobjective maximization problems, Angular synchronization by eigenvectors and semidefinite programming, Minimal zeros of copositive matrices, On judicious bisections of graphs, Lifting and separation procedures for the cut polytope, Gap inequalities for non-convex mixed-integer quadratic programs, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, Computing the Grothendieck constant of some graph classes, Coding of image feature descriptors for distributed rate-efficient visual correspondences, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, Geometric rounding: A dependent randomized rounding scheme, Revised GRASP with path-relinking for the linear ordering problem, Approximation algorithms for indefinite complex quadratic maximization problems, Global quadratic minimization over bivalent constraints: necessary and sufficient global optimality condition, Knapsack problem with probability constraints, Optimality theorems for convex semidefinite vector optimization problems, An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach, Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme, Testing the nullspace property using semidefinite programming, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, On the security of Goldreich's one-way function, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, A fresh variational-analysis look at the positive semidefinite matrices world, A new discrete filled function method for solving large scale max-cut problems, Compressed labeling on distilled labelsets for multi-label learning, Improved estimation of duality gap in binary quadratic programming using a weighted distance measure, Convergence and approximation in potential games, A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations, Moment inequalities for sums of random matrices and their applications in optimization, New geometry-inspired relaxations and algorithms for the metric Steiner tree problem, Online maximum directed cut, On duality gap in binary quadratic programming, Bisections of graphs, Global optimality conditions and optimization methods for quadratic integer programming problems, Solving the maxcut problem by the global equilibrium search, Binary positive semidefinite matrices and associated integer polytopes, Approximation bounds for sparse principal component analysis, Stable optimizationless recovery from phaseless linear measurements, Model decomposition and reduction tools for large-scale networks in systems biology, A convex relaxation bound for subgraph isomorphism, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, Simultaneous approximation of multi-criteria submodular function maximization, Stochastic and semidefinite optimization for scheduling in orthogonal frequency division multiple access networks, Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques, A polynomial case of convex integer quadratic programming problems with box integer constraints, Chance constrained \(0-1\) quadratic programs using copulas, On Laplacian spectra of parametric families of closely connected networks with application to cooperative control, Approximating Max NAE-\(k\)-SAT by anonymous local search, Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability, Computing the partition function for graph homomorphisms, Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming, On semidefinite least squares and minimal unsatisfiability, Max-cut and extendability of matchings in distance-regular graphs, Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games, Disentangling orthogonal matrices, Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, Intrinsic representation of tangent vectors and vector transports on matrix manifolds, Canonical dual approach to solving the maximum cut problem, Mathematical vanity plates, A new Lagrangian net algorithm for solving max-bisection problems, An efficient Lagrangian smoothing heuristic for max-cut, A class of semidefinite programs with rank-one solutions, A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, An optimal approach for the critical node problem using semidefinite programming, On box-constrained total least squares problem, Approximation and hardness results for the max \(k\)-uncut problem, Using the eigenvalue relaxation for binary least-squares estimation problems, Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems, A note on unique games, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Conic mixed-integer rounding cuts, A genetic system based on simulated crossover of sequences of two-bit genes, Measure concentration in optimization, Semidefinite programming in combinatorial optimization, Interior-point methods: An old and new approach to nonlinear programming, Anti-coordination and social interactions, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, Efficient rank reduction of correlation matrices, On approximating complex quadratic optimization problems via semidefinite programming relaxations, Max Horn SAT and the minimum cut problem in directed hypergraphs, Approximating the independence number via the \(\vartheta\)-function, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property, Estimating the conservatism of Popov's criterion for real parametric uncertainties, Key leaders in social networks, Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel, The lazy bureaucrat scheduling problem, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, An approximation algorithm for scheduling two parallel machines with capacity constraints., On the hardness of efficiently approximating maximal non-\(L\) submatrices., Complexity results on a paint shop problem., The spherical constraint in Boolean quadratic programs, Cardinality constrained minimum cut problems: complexity and algorithms., The capacitated max \(k\)-cut problem, On the complexity of optimization over the standard simplex, An efficient solver for weighted Max-SAT, A modified VNS metaheuristic for max-bisection problems, A discrete filled function algorithm for approximate global solutions of max-cut problems, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, Sums of squares based approximation algorithms for MAX-SAT, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), Hybridizing the cross-entropy method: An application to the max-cut problem, High-multiplicity cyclic job shop scheduling, Maximum cut in fuzzy nature: models and algorithms, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, Pseudo-Boolean optimization, Semidefinite programming for discrete optimization and matrix completion problems, Small space representations for metric min-sum \(k\)-clustering and their applications, Semi-definite relaxation algorithm of multiple knapsack problem, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, A parallel interior point decomposition algorithm for block angular semidefinite programs, Noise stability of functions with low influences: invariance and optimality, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Convex relaxations for mixed integer predictive control, Approximation algorithms for MAX RES CUT with limited unbalanced constraints, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Solutions to quadratic minimization problems with box and integer constraints, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, Extensions on ellipsoid bounds for quadratic integer programming, A new branch and bound method with pretreatment for the binary quadratic programming, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs, Anti-modularity and anti-community detecting in complex networks, Valid inequalities for mixed integer linear programs, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, Community detection in sparse networks via Grothendieck's inequality, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Wireless capacity with arbitrary gain matrix, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, A geometric characterization of ``optimality-equivalent relaxations, Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Alphabet indexing for approximating features of symbols, Spectral partitioning with multiple eigenvectors, Path optimization for graph partitioning problems, Learning action models from plan examples using weighted MAX-SAT, A global continuation algorithm for solving binary quadratic programming problems, Some APX-completeness results for cubic graphs, Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Scheduling projects with stochastic activity duration to maximize expected net present value, Exploiting special structure in semidefinite programming: a survey of theory and applications, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Tight bound on Johnson's algorithm for maximum satisfiability, Interior-point methods, Combinatorial optimization: current successes and directions for the future, Pivot versus interior point methods: Pros and cons, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Semidefinite programming, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Approximation algorithms for maximum linear arrangement, A note on approximating Max-Bisection on regular graphs, On the Slater condition for the SDP relaxations of nonconvex sets, Distance realization problems with applications to internet tomography, A randomized approximation scheme for metric MAX-CUT, Heuristics for semirandom graph problems, Rank-one LMI approach to simultaneous stabilization of linear systems., On bounded occurrence constraint satisfaction, Improved approximation algorithms for maximum graph partitioning problems, Robust sub-Gaussian estimation of a mean vector in nearly linear time, On regularity of Max-CSPs and Min-CSPs, A self-consistent-field iteration for MAXBET with an application to multi-view feature extraction, SDP-based bounds for graph partition via extended ADMM, Improved approximations for max set splitting and max NAE SAT, Approximation algorithm for MAX DICUT with given sizes of parts, Cluster graph modification problems, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, A note on computing the smallest conic singular value, Bifurcation analysis of eight coupled degenerate optical parametric oscillators, Approximately nearest neighborhood image search using unsupervised hashing via homogeneous kernels, Gaussian noise sensitivity and Fourier tails, On the exact solution of the no-wait flow shop problem with due date constraints, Some geometric results in semidefinite programming, Approximating the weighted maximin dispersion problem over an \(\ell _p\)-ball: SDP relaxation is misleading, New algorithms for the weighted maximum cut problem on graphs, Computational study of valid inequalities for the maximum \(k\)-cut problem, Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs, Randomized competitive analysis for two server problems, A semidefinite approach to the $K_i$-cover problem, The matching problem has no small symmetric SDP, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Solving \(k\)-cluster problems to optimality with semidefinite programming, Maximum directed cuts in graphs with degree constraints, A ``joint + marginal heuristic for 0/1 programs, The convex geometry of linear inverse problems, Shape-based object detection via boundary structure segmentation, On solving biquadratic optimization via semidefinite relaxation, Approximation algorithm for a class of global optimization problems, Newsvendor games: convex optimization of centralized inventory operations, Using negative curvature in solving nonlinear programs, Intractability of min- and max-cut in streaming graphs, Minimizing worst-case and average-case makespan over scenarios, A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section, Finding the maximum cut by the greedy algorithm, Ensemble clustering using semidefinite programming with applications, Global optimization in Hilbert space, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Affine reductions for LPs and SDPs, Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP, Notes on computational-to-statistical gaps: predictions using statistical physics, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, Bisections of graphs without \(K_{2, l}\), Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Simple approximation algorithms for balanced MAX~2SAT, Topology optimization via sequential integer programming and canonical relaxation algorithm, Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming, Simplicial faces of the set of correlation matrices, Fast binary embeddings with Gaussian circulant matrices: improved bounds, A semidefinite programming method for integer convex quadratic minimization, Random Laplacian matrices and convex relaxations, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, Binary quadratic optimization problems that are difficult to solve by conic relaxations, Conic programming: infeasibility certificates and projective geometry, Maximally stable Gaussian partitions with discrete applications, A discrete dynamic convexized method for the max-cut problem, Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, An improved semidefinite programming relaxation for the satisfiability problem, Parametric Lagrangian dual for the binary quadratic programming problem, Convex reformulation for binary quadratic programming problems via average objective value maximization, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Robust optimality of Gaussian noise stability, Penalized semidefinite programming for quadratically-constrained quadratic optimization, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?, A polynomial-time algorithm to find an equitable home--away assignment, Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval, Polyhedral approximations of the semidefinite cone and their application, Phase retrieval with PhaseLift algorithm, An efficient method for convex constrained rank minimization problems based on DC programming, Convex relaxation methods for community detection, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs, \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel, Efficient semidefinite branch-and-cut for MAP-MRF inference, Approximating graph-constrained max-cut, Semidefinite and linear programming integrality gaps for scheduling identical machines, A priori TSP in the scenario model, An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation, Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, Computing in combinatorial optimization, Gaussian discrepancy: a probabilistic relaxation of vector balancing, An approximation algorithm for the maximum spectral subgraph problem, Parameterized complexity of multi-node hubs, Approximating a generalization of MAX 2SAT and MIN 2SAT, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs, Private non-monotone submodular maximization, On approximation of max-vertex-cover, SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs, Robust group synchronization via cycle-edge message passing, Classical symmetries and the quantum approximate optimization algorithm, Empirical performance bounds for quantum approximate optimization, Quantum circuit design for objective function maximization in gate-model quantum computers, Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem, On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs, Convex graph invariant relaxations for graph edit distance, Stochastic Quadratic Knapsack with Recourse, Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems, On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, Jordan-algebraic aspects of optimization: randomization, A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access, Grothendieck-Type Inequalities in Combinatorial Optimization, Matrix Relaxations in Combinatorial Optimization, Simultaneous Approximation of Constraint Satisfaction Problems, Spotting Trees with Few Leaves, Approximating CSPs Using LP Relaxation, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Approximation Limits of Linear Programs (Beyond Hierarchies), A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds, A note on approximating quadratic programming with rank constraint, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Maximization of Matrix Trace Function of Product Stiefel Manifolds, Fast implementation for semidefinite programs with positive matrix completion, Are Stable Instances Easy?, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Max-Cut Under Graph Constraints, An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, Finite quantum tomography and semidefinite programming, A continuation algorithm for max-cut problem, Judicious partitions of directed graphs, Stable Camera Motion Estimation Using Convex Programming, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, A note on the Lasserre hierarchy for different formulations of the maximum independent set problem, On recovery guarantees for angular synchronization, Computing the largest bond and the maximum connected cut of a graph, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Reinforcement learning for combinatorial optimization: a survey, The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables, \texttt{EXPEDIS}: an exact penalty method over discrete sets, Computational study of a branching algorithm for the maximum \(k\)-cut problem, An approximation algorithm for maxk-uncut with capacity constraints, An optimal streaming algorithm for non-submodular functions maximization on the integer lattice, Super-polynomial approximation branching algorithms, Ellipsoid Bounds for Convex Quadratic Integer Programming, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, Computation of the phase and gain margins of MIMO control systems, Benchmarking the quantum approximate optimization algorithm, Approximation and Hardness Results for the Max k-Uncut Problem, Optimal Learning in Linear Regression with Combinatorial Feature Selection, Approximating Alternative Solutions, New bounds for nonconvex quadratically constrained quadratic programming, Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting), Pareto robust optimization on Euclidean vector spaces, Linear programing relaxations for a strategic pricing problem in electricity markets, Calmness of partial perturbation to composite rank constraint systems and its applications, A priori TSP in the Scenario Model, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, A semidefinite relaxation based global algorithm for two-level graph partition problem, New algorithms for a simple measure of network partitioning, Profit maximization in social networks and non-monotone DR-submodular maximization, On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy, A semidefinite programming approach to the hypergraph minimum bisection problem, Low-Rank Matrix Iteration Using Polynomial-Filtered Subspace Extraction, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm, Stochastic Organization of Output Codes in Multiclass Learning Problems, A projected gradient algorithm for solving the maxcut SDP relaxation, Second order cone programming relaxation of nonconvex quadratic optimization problems, Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment, Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA, Computational experience with a SDP-based algorithm for maximum cut with limited unbalance, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Introduction to Semidefinite, Conic and Polynomial Optimization, Convex Relaxations and Integrality Gaps, Relaxations of Combinatorial Problems Via Association Schemes, A “Joint+Marginal” Approach in Optimization, Self-Regular Interior-Point Methods for Semidefinite Optimization, Block Coordinate Descent Methods for Semidefinite Programming, Projection Methods in Conic Optimization, Semidefinite Programming and Constraint Programming, Latest Developments in the SDPA Family for Solving Large-Scale SDPs, Computational Approaches to Max-Cut, Global Approaches for Facility Layout and VLSI Floorplanning, Euclidean Distance Matrices and Applications, Tight Bounds on the Radius of Nonsingularity, Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems, Robustly Solvable Constraint Satisfaction Problems, From Graph Orientation to the Unweighted Maximum Cut, On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming, Approximability Distance in the Space of H-Colourability Problems, New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials, A Coordinate Ascent Method for Solving Semidefinite Relaxations of Non-convex Quadratic Integer Programs, Diagonally Dominant Programming in Distance Geometry, On Khot’s unique games conjecture, One-Bit Compressed Sensing by Linear Programming, A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs, Efficient Rounding for the Noncommutative Grothendieck Inequality, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Semidefinite programming based approaches to the break minimization problem, Approximating Max Cut with Limited Unbalance, New bounds for the maximum cut problem, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation, Binary vectors for fast distance and similarity estimation, An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Eigenvalues of Cayley graphs, Community detection with a subsampled semidefinite program, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, On computational capabilities of Ising machines based on nonlinear oscillators, Approximation algorithms for two variants of correlation clustering problem, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Stochastic budget optimization in internet advertising, Discrete dynamical system approaches for Boolean polynomial optimization, Parameterized algorithms for min-max multiway cut and list digraph homomorphism, A simple method for convex optimization in the oracle model, Three conjectures in extremal spectral graph theory, Exploiting sparsity for the min \(k\)-partition problem, Solving rank-constrained semidefinite programs in exact arithmetic, An exact semidefinite programming approach for the max-mean dispersion problem, A class of spectral bounds for max \(k\)-cut, Inapproximability ratios for crossing number, Theorems of the alternative for conic integer programming, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, A new approximation hierarchy for polynomial conic optimization, The geometry of SDP-exactness in quadratic optimization, Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming, Mean estimation with sub-Gaussian rates in polynomial time, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, On lazy bureaucrat scheduling with common deadlines, Submodular optimization problems and greedy strategies: a survey, A representation theory perspective on simultaneous alignment and classification, Drawing (complete) binary tanglegrams, Convolutional neural network learning for generic data classification, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, The maximum cut problem on blow-ups of multiprojective spaces, A tight \(\sqrt{2} \)-approximation for linear 3-cut, Improved semidefinite bounding procedure for solving max-cut problems to optimality, Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems, Cuts in undirected graphs. I, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Additive approximation algorithms for modularity maximization, On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities, Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound, Computational protein design as an optimization problem, Approximation algorithms for maximum cut with limited unbalance, Approximating the fixed linear crossing number, On a polynomial fractional formulation for independence number of a graph, \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion, Exact MAX-2SAT solution via lift-and-project closure, On the asymptotic minimum number of monochromatic 3-term arithmetic progressions, Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation, Round robin scheduling -- a survey, Dimension reduction by random hyperplane tessellations, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Triangle-free subcubic graphs with minimum bipartite density, Exploiting semidefinite relaxations in constraint programming, A multiple penalty function method for solving max-bisection problems, Exploring the relationship between max-cut and stable set relaxations, Lagrangian smoothing heuristics for Max-cut, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Robust global optimization with polynomials, Approximation algorithms for the bi-criteria weighted MAX-CUT problem, Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming, Frequency-hopping code design for Target detection via optimization theory, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Lower bound improvement and forcing rule for quadratic binary programming, Semidefinite programming relaxations and algebraic optimization in control, A novel formulation of the max-cut problem and related algorithm, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, Phase recovery, MaxCut and complex semidefinite programming, Phase retrieval from coded diffraction patterns, Barvinok's naive algorithm in distance geometry, Approximating max-cut under graph-MSO constraints, A simple algorithm for the multiway cut problem, Some observations on the smallest adjacency eigenvalue of a graph, Volume computation for sparse Boolean quadric relaxations, Conic relaxation approaches for equal deployment problems, Approximation algorithms for connected maximum cut and related problems, Theory versus practice in annealing-based quantum computing, Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation, Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting, Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem, On fractional cut covers, Exact recovery in the Ising blockmodel, Immediate schedule adjustment and semidefinite relaxation, A max-cut approach to heterogeneity in cryo-electron microscopy, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms, Hypergraph cuts above the average, Sharing hash codes for multiple purposes, A semidefinite optimization approach for the single-row layout problem with unequal dimensions, Efficient algorithms for online decision problems, Cuts for mixed 0-1 conic programming, Oblivious algorithms for the maximum directed cut problem, Robust computation of linear models by convex relaxation, Speeding up a memetic algorithm for the max-bisection problem, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems, Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, On the Complexity of Random Satisfiability Problems with Planted Solutions, Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming, Lifting for Simplicity: Concise Descriptions of Convex Sets, On the Computability of Continuous Maximum Entropy Distributions with Applications, Problems and results on judicious partitions, On the optimality of the random hyperplane rounding technique for MAX CUT, The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, A Unified Framework for Structured Graph Learning via Spectral Constraints, Disordered systems insights on computational hardness, Fast Distributed Approximation for Max-Cut, A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ, Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Finding Sparse Solutions for Packing and Covering Semidefinite Programs, Symbolic computation in hyperbolic programming, The interior-point revolution in optimization: History, recent developments, and lasting consequences, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, Cutting Plane Generation through Sparse Principal Component Analysis, A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity, Unifying Online and Offline Preference for Social Link Prediction, Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective, Optimization on the Euclidean Unit Sphere, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Quantum Annealing versus Digital Computing, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Detection of core–periphery structure in networks using spectral methods and geodesic paths, Optimal arrangements of classical and quantum states with limited purity, Constrained Submodular Maximization via a Nonsymmetric Technique, Unnamed Item, Maximum Cut Parameterized by Crossing Number, Approximate Global Minimizers to Pairwise Interaction Problems via Convex Relaxation, Bounds for Random Binary Quadratic Programs, Randomized Algorithms for Lexicographic Inference, Proof Complexity Meets Algebra, Assortment Optimization Under the Paired Combinatorial Logit Model, Dynamical Systems Theory and Algorithms for NP-hard Problems, Randomized Competitive Analysis for Two-Server Problems, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Approximation Algorithms for CSPs, Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection, Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph, A guide to conic optimisation and its applications, Spectral Relaxations and Branching Strategies for Global Optimization of Mixed-Integer Quadratic Programs, A framework for solving mixed-integer semidefinite programs, Semidefinite relaxation for the total least squares problem with Tikhonov-like regularization, Parameterized Complexity of Multi-Node Hubs, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, Three candidate plurality is stablest for small correlations, Approximation algorithms, Cone-LP's and semidefinite programs: Geometry and a simplex-type method, Iterated linear optimization, Sums of Squares and Sparse Semidefinite Programming, Unnamed Item, Unnamed Item, A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints, Semidefinite relaxation approximation for multivariate bi‐quadratic optimization with quadratic constraints, Learning Binary Hash Codes for Large-Scale Image Search, Approximating the 2-catalog segmentation problem using semidefinite programming relaxations, On the Simplicity and Conditioning of Low Rank Semidefinite Programs, Interior Point Methods for Nonlinear Optimization, Community Detection and Stochastic Block Models, Semidefinite relaxation and nonconvex quadratic optimization, A branch‐and‐price approach to k‐clustering minimum biclique completion problem, Randomized heuristics for the Max-Cut problem, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Dimension Reduction for Polynomials over Gaussian Space and Applications, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Regularity radius: Properties, approximation and a not a priori exponential algorithm, Rank Optimality for the Burer--Monteiro Factorization, Spectral bounds for the maximum cut problem, Online Submodular Maximization with Preemption, On semidefinite bounds for maximization of a non-convex quadratic objective over thel1unit ball, A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM, Sherali-adams strikes back, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Simultaneous max-cut is harder to approximate than max-cut, Simplex Transformations and the Multiway Cut Problem, Efficient Online Linear Optimization with Approximation Algorithms, Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties, Semidefinite Programming and Nash Equilibria in Bimatrix Games, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, A Newton-bracketing method for a simple conic optimization problem, Scalable Semidefinite Programming, Non-unique games over compact groups and orientation estimation in cryo-EM, Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Mixed linear and semidefinite programming for combinatorial and quadratic optimization, Revisiting maximum satisfiability and related problems in data streams, BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Spotting Trees with Few Leaves, Unnamed Item, An augmented Lagrangian method for optimization problems with structured geometric constraints, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Evaluating approximations of the semidefinite cone with trace normalized distance, Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms, An introduction to variational quantum algorithms for combinatorial optimization problems, A practitioner’s guide to quantum algorithms for optimisation problems, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, Sum of Squares Bounds for the Empty Integral Hull Problem, An entropy-regularized ADMM for binary quadratic programming, Research trends in combinatorial optimization, A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints, Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations, A semismooth Newton based dual proximal point algorithm for maximum eigenvalue problem, A new global algorithm for max-cut problem with chordal sparsity, Graph partitioning: an updated survey, Revisiting maximum satisfiability and related problems in data streams, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, A unified approach to synchronization problems over subgroups of the orthogonal group, A preconditioned iterative interior point approach to the conic bundle subproblem, New results for MaxCut in H$H$‐free graphs, Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization, Worst-case subexponential attacks on PRGs of constant degree or constant locality, Elliptic polytopes and invariant norms of linear operators, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization, An effective global algorithm for worst-case linear optimization under polyhedral uncertainty, New semidefinite relaxations for a class of complex quadratic programming problems, A binary search double greedy algorithm for non-monotone DR-submodular maximization, Max-Cut via Kuramoto-Type Oscillators, Provable Phase Retrieval with Mirror Descent, A universal quantum algorithm for weighted maximum cut and Ising problems, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Unnamed Item, Exact SDP relaxations for quadratic programs with bipartite graph structures, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Complexity of maximum cut on interval graphs, On the complexity of binary polynomial optimization over acyclic hypergraphs, Approximating sparse quadratic programs, Invariants of SDP exactness in quadratic programming, On optimal universal first-order methods for minimizing heterogeneous sums, Mathematics of computation through the lens of linear equations and lattices, A quadratic simplex algorithm for primal optimization over zero-one polytopes, Unnamed Item, Approximation algorithms for quantum many-body problems, Unnamed Item, Dilations, Linear Matrix Inequalities, the Matrix Cube Problem and Beta Distributions, Recent Theoretical Advances in Non-Convex Optimization, Grothendieck’s Theorem, past and present, EXACT CALCULATION OF ROBUSTNESS OF ENTANGLEMENT VIA CONVEX SEMI-DEFINITE PROGRAMMING, Constructing test functions for global optimization using continuous formulations of graph problems, On the Approximability of Presidential Type Predicates, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, Cones of multipowers and combinatorial optimization problems, A probabilistic result for the max-cut problem on random graphs, LMI approximations for the radius of the intersection of ellipsoids: Survey., Computational and statistical tradeoffs via convex relaxation, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, Semidefinite programming and combinatorial optimization, Graphs with Large Girth Not Embeddable in the Sphere, A filled function method for quadratic programs with binary constraints†, The omnipresence of Lagrange, On judicious bipartitions of graphs, MAX SAT approximation beyond the limits of polynomial-time approximation, A spectral partitioning algorithm for maximum directed cut problem, New algorithms for a simple measure of network partitioning, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Phase Retrieval via Matrix Completion, Spectrahedral cones generated by rank \(1\) matrices, Semidefinite relaxations for partitioning, assignment and ordering problems, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, Sum-of-squares hierarchies for binary polynomial optimization, Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Semidefinite relaxations for partitioning, assignment and ordering problems, ADMM for multiaffine constrained optimization, Sum-of-squares hierarchies for binary polynomial optimization, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, MAX k‐CUT and approximating the chromatic number of random graphs, Benchmark Problems for Phase Retrieval, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, Inhomogeneous polynomial optimization over a convex set: An approximation approach, Subsampling Algorithms for Semidefinite Programming, Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP, Probability Bounds for Polynomial Functions in Random Variables, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, On Some Open Questions for Ramsey and Folkman Numbers, Global Registration of Multiple Point Clouds Using Semidefinite Programming, Unnamed Item, Unnamed Item, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Local Density Estimation in High Dimensions, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
Uses Software
