Cover Image

Practical Experience with Stable Set and Coloring Relaxations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pucher, Dunja, Rendl, Franz
Format:	Preprint
Published:	2024
Subjects:	Optimization and Control 90C27, 90C22
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
by: Gaar, Elisabeth, et al.
Published: (2024)

On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
by: Gaar, Elisabeth
Published: (2020)

SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy
by: Sinjorgo, Lennart, et al.
Published: (2025)

Edge expansion of a graph: SDP-based computational strategies
by: Gupte, Akshay, et al.
Published: (2024)

SDP Approach to Quadratic Vertex-Disjoint Paths Problem
by: Xu, Mingming, et al.
Published: (2026)

On exactness of SDP relaxation for the maximum cut problem
by: Bhardwaj, Avinash, et al.
Published: (2025)

Quantum and Simulated Annealing-Based Iterative Algorithms for QUBO Relaxations of the Sparsest $k$-Subgraph Problem
by: Bihani, Omkar, et al.
Published: (2025)

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method
by: Jung, Woosuk L., et al.
Published: (2023)

Application of the Lovász-Schrijver Lift-and-Project Operator to Compact Stable Set Integer Programs
by: Battista, Federico, et al.
Published: (2024)

Projection, Degeneracy, and Singularity Degree for Spectrahedra
by: Im, Haesol, et al.
Published: (2024)

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
by: Au, Yu Hin, et al.
Published: (2025)

Quantum computing and the stable set problem
by: Krpan, Aljaž, et al.
Published: (2024)

Strong SDP based bounds on the cutwidth of a graph
by: Gaar, Elisabeth, et al.
Published: (2023)

Relaxations for binary polynomial optimization via signed certificates
by: Xu, Liding, et al.
Published: (2024)

On generators of $k$-PSD closures of the positive semidefinite cone
by: Bhardwaj, Avinash, et al.
Published: (2024)

A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
by: Au, Yu Hin, et al.
Published: (2025)

Separable QCQPs and Their Exact SDP Relaxations
by: Kojima, Masakazu, et al.
Published: (2026)

Constructing QCQP Instances Equivalent to Their SDP Relaxations
by: Kojima, Masakazu, et al.
Published: (2025)

Semidefinite approximations for bicliques and biindependent pairs
by: Laurent, Monique, et al.
Published: (2023)

Extending Exact Convex Relaxations of Quadratically Constrained Quadratic Programs
by: Kojima, Masakazu, et al.
Published: (2025)

A Low-rank Augmented Lagrangian Method for Polyhedral-SDP and Moment-SOS Relaxations of Polynomial Optimization
by: Hou, Di, et al.
Published: (2025)

Globally Solving Concave Quadratic Programs via Doubly Nonnegative Relaxation
by: Qu, Zheng, et al.
Published: (2023)

Computational complexity of sum-of-squares bounds for copositive programs
by: Palomba, Marilena, et al.
Published: (2025)

Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem
by: Barkel, Mathijs, et al.
Published: (2026)

Evacuation Planning on Time-Expanded Networks with Integrated Wildfire Information
by: Borgwardt, Steffen, et al.
Published: (2024)

Sparse Polynomial Optimization with Unbounded Sets
by: Huang, Lei, et al.
Published: (2024)

Weighted Geometric Mean, Minimum Mediated Set, and Optimal Simple Second-Order Cone Representation
by: Wang, Jie
Published: (2022)

Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs
by: Yildirim, E. Alper
Published: (2025)

A Bilevel Hierarchy of Strengthened Complex Moment Relaxations for Complex Polynomial Optimization
by: Wang, Jie
Published: (2024)

Real-time solution of quadratic optimization problems with banded matrices and indicator variables
by: Gomez, Andres, et al.
Published: (2024)

Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization
by: Salloum, Hadi, et al.
Published: (2025)

Lagrangian Reformulation for Nonconvex Optimization: Tailoring Problems to Specialized Solvers
by: Quintero, Rodolfo A., et al.
Published: (2024)

Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks
by: Azuma, Godai, et al.
Published: (2025)

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment under Consideration of Single Room Entitlements
by: Brandt, Tabea, et al.
Published: (2023)

Solving Cutting Stock Problems via an Extended Ryan-Foster Branching Scheme and Fast Column Generation
by: da Silva, Renan F. F., et al.
Published: (2023)

A Canceling Heuristic for the Directed Traveling Salesman Problem
by: Borgwardt, Steffen, et al.
Published: (2026)

Generalizations of Total Dual Integrality
by: Guenin, Bertrand, et al.
Published: (2025)

The link between $1$-norm approximation and effective Positivstellensatze for the hypercube
by: de Klerk, Etienne, et al.
Published: (2024)

An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
by: Laurent, Monique, et al.
Published: (2024)

Piecewise SOS-Convex Moment Optimization and Applications via Exact Semi-Definite Programs
by: Huang, Queenie Yingkun, et al.
Published: (2024)