Imagen de Portada

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Au, Yu Hin, Tunçel, Levent
Formato:	Preprint
Publicado:	2025
Materias:	Combinatorics Computational Complexity Discrete Mathematics Optimization and Control 90C22, 90C27
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
por: Au, Yu Hin, et al.
Publicado: (2023)

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
por: Au, Yu Hin, et al.
Publicado: (2024)

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

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

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

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

Generalizations of Total Dual Integrality
por: Guenin, Bertrand, et al.
Publicado: (2025)

Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem
por: Kim, Junyoung, et al.
Publicado: (2024)

Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm
por: Masing, Berenike, et al.
Publicado: (2024)

Everything is possible: constructing spectrahedra with prescribed facial dimensions
por: Roshchina, Vera, et al.
Publicado: (2023)

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

Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models
por: Bui, Quang Minh, et al.
Publicado: (2024)

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

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

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

Practical Experience with Stable Set and Coloring Relaxations
por: Pucher, Dunja, et al.
Publicado: (2024)

Relaxation strength for multilinear optimization: McCormick strikes back
por: Schutte, Emily, et al.
Publicado: (2023)

On the redundancy of transitivity constraints in the clique partitioning problem
por: Sukegawa, Noriyoshi
Publicado: (2026)

Rescue Craft Allocation in Tidal Waters of the North and Baltic Sea
por: Mucke, Tom, et al.
Publicado: (2024)

On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
por: Au, Yu Hin, et al.
Publicado: (2020)

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

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

Benders decomposition algorithms for minimizing the spread of harmful contagions in networks
por: Tanınmış, Kübra, et al.
Publicado: (2023)

A more efficient reformulation of complex SDP as real SDP
por: Wang, Jie
Publicado: (2023)

An extended version of the Ordered Median Tree Location Problem including appendices and detailed computational results
por: Pozo, Miguel A., et al.
Publicado: (2022)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
por: Ammann, Sabrina C. L., et al.
Publicado: (2024)

Finding Short Paths on Simple Polytopes
por: Black, Alexander E., et al.
Publicado: (2026)

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

The rainbow covering number of clean tangled clutters
por: Abdi, Ahmad, et al.
Publicado: (2025)

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

Totally $Δ$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
por: McFarland, Caleb
Publicado: (2026)

Graph burning: an overview of mathematical programs
por: Cajica-Maceda, Lourdes Beatriz, et al.
Publicado: (2025)

Convex quadratic sets and the complexity of mixed integer convex quadratic programming
por: Del Pia, Alberto
Publicado: (2023)

Extending the definition of set tolerances
por: Jäger, Gerold, et al.
Publicado: (2024)

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

Large independent sets in recursive Markov random graphs
por: Gupte, Akshay, et al.
Publicado: (2022)

Supermodular Maximization with Cardinality Constraints
por: Chen, Xujin, et al.
Publicado: (2025)

Competing for the most profitable tour: The orienteering interdiction game
por: Álvarez-Miranda, Eduardo, et al.
Publicado: (2024)

The Schrijver system of the length polyhedron of an interval order
por: Kézdy, André E., et al.
Publicado: (2024)