Buchumschlag

Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Barkel, Mathijs, Sotirov, Renata
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Optimization and Control 05C15, 05C17, 90C22, 90C27, 90C35
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Cuts and semidefinite liftings for the complex cut polytope
von: Sinjorgo, Lennart, et al.
Veröffentlicht: (2024)

On exactness of SDP relaxation for the maximum cut problem
von: Bhardwaj, Avinash, et al.
Veröffentlicht: (2025)

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

A Canceling Heuristic for the Directed Traveling Salesman Problem
von: Borgwardt, Steffen, et al.
Veröffentlicht: (2026)

Non-Attainment of Minima in Non-Polyhedral Conic Optimization: A Robust SOCP Example
von: Nguyen, Vinh
Veröffentlicht: (2025)

On generalized KKT points for the Motzkin-Straus program
von: Beretta, G., et al.
Veröffentlicht: (2023)

Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
von: Tang, Tianyun, et al.
Veröffentlicht: (2024)

Beyond binarity: Semidefinite programming for ternary quadratic problems
von: de Meijer, Frank, et al.
Veröffentlicht: (2026)

SDP Approach to Quadratic Vertex-Disjoint Paths Problem
von: Xu, Mingming, et al.
Veröffentlicht: (2026)

Semidefinite approximations for bicliques and biindependent pairs
von: Laurent, Monique, et al.
Veröffentlicht: (2023)

Fixed Topology Minimum-Length Trees with Neighborhoods
von: Blanco, Víctor, et al.
Veröffentlicht: (2024)

Getting to the Root of the Problem: Sums of Squares for Limits of Trees
von: Brosch, Daniel, et al.
Veröffentlicht: (2024)

A preconditioned augmented Lagrangian method for solving semidefinite programming problems
von: Tang, Tianyun, et al.
Veröffentlicht: (2026)

Splitting Algorithms for Distributionally Robust Optimization
von: Briceño-Arias, Luis, et al.
Veröffentlicht: (2024)

A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis
von: Zhang, Rui-Jin, et al.
Veröffentlicht: (2025)

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

On generators of $k$-PSD closures of the positive semidefinite cone
von: Bhardwaj, Avinash, et al.
Veröffentlicht: (2024)

Improved Bounds for the Ultimate Independence Ratio of Odd Wheels
von: Clow, Alexander, et al.
Veröffentlicht: (2025)

Solving clustered low-rank semidefinite programs arising from polynomial optimization
von: Leijenhorst, Nando, et al.
Veröffentlicht: (2022)

A squared smoothing Newton method for semidefinite programming
von: Liang, Ling, et al.
Veröffentlicht: (2023)

Computational complexity of sum-of-squares bounds for copositive programs
von: Palomba, Marilena, et al.
Veröffentlicht: (2025)

Finding Short Paths on Simple Polytopes
von: Black, Alexander E., et al.
Veröffentlicht: (2026)

New Formulation for Coloring Circle Graphs and its Application to Capacitated Stowage Stack Minimization
von: Tanaka, Masato, et al.
Veröffentlicht: (2021)

On seeded subgraph-to-subgraph matching: The ssSGM Algorithm and matchability information theory
von: Meng, Lingyao, et al.
Veröffentlicht: (2023)

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

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

T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
von: Marumo, Hiroki, et al.
Veröffentlicht: (2024)

A semidefinite programming hierarchy for covering problems in discrete geometry
von: Riener, Cordian, et al.
Veröffentlicht: (2023)

Conductance Estimation in Digraphs: Submodular Transformation, Lovász Extension and Dinkelbach Iteration
von: Shao, Sihong, et al.
Veröffentlicht: (2025)

Second-order sequential optimality conditions for nonlinear semidefinite optimization problems
von: Li, Huimin, et al.
Veröffentlicht: (2025)

Adjustable Robust Nonlinear Network Design Without Controllable Elements under Load Scenario Uncertainties
von: Thürauf, Johannes, et al.
Veröffentlicht: (2024)

On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems
von: Borgwardt, Steffen, et al.
Veröffentlicht: (2025)

Solving exact and noisy rank-one tensor completion with semidefinite programming
von: Cifuentes, Diego, et al.
Veröffentlicht: (2025)

Multi-objective stochastic linear programming with recourse and flexible decision making
von: Hamel, Andreas H., et al.
Veröffentlicht: (2024)

A Matrix Optimization Method for Blind Extraction of External Equitable Partitions from Low Pass Graph Signals
von: Teng, Wenshun, et al.
Veröffentlicht: (2025)

On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials
von: Niu, Yi-Shuai, et al.
Veröffentlicht: (2018)

A new dual spectral projected gradient method for log-determinant semidefinite programming with hidden clustering structures
von: Namchaisiri, Charles, et al.
Veröffentlicht: (2024)

Edge expansion of a graph: SDP-based computational strategies
von: Gupte, Akshay, et al.
Veröffentlicht: (2024)

Projection, Degeneracy, and Singularity Degree for Spectrahedra
von: Im, Haesol, et al.
Veröffentlicht: (2024)

A simulation-optimization approach for fractional, profitability-oriented inventory control under service-level type constraints
von: Sun, Tianxiao, et al.
Veröffentlicht: (2026)