Cover Image

The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hou, Jiaxin, Soh, Yong Sheng, Varvitsiotis, Antonios
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control Data Structures and Algorithms Information Theory Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Matrices over a Polynomial Ring with Restricted Subdeterminants
by: Celaya, Marcel, et al.
Published: (2023)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Min-Max Connected Multiway Cut
by: Tiwary, Hans Raj, et al.
Published: (2026)

A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
by: Kuhlmann, Stefan, et al.
Published: (2025)

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
by: Gao, Xuan-Zhao, et al.
Published: (2024)

Optimal Micro-Transit Zoning via Clique Generation and Integer Programming
by: Hu, Hins, et al.
Published: (2025)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
by: Li, Gen, et al.
Published: (2023)

Gap-Free Clustering: Sensitivity and Robustness of SDP
by: Zurek, Matthew, et al.
Published: (2023)

Approximate Message Passing for Quantum State Tomography
by: Siekierski, Noah, et al.
Published: (2025)

BalLOT: Balanced $k$-means clustering with optimal transport
by: Luo, Wenyan, et al.
Published: (2025)

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

Total Matching and Subdeterminants
by: Ferrarini, Luca, et al.
Published: (2023)

A Primal-Dual Framework for Symmetric Cone Programming
by: Zheng, Jiaqi, et al.
Published: (2024)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Integer programs with bounded subdeterminants and two nonzeros per row
by: Fiorini, Samuel, et al.
Published: (2021)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

Prefix-bounded matrices
by: Borsik, Nóra A., et al.
Published: (2025)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

Integer programs with nearly totally unimodular matrices: the cographic case
by: Aprile, Manuel, et al.
Published: (2024)

Totally $Δ$-modular IPs with two non-zeros in most rows
by: Kober, Stefan
Published: (2024)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, et al.
Published: (2023)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
by: Ahmadypour, Niloufar, et al.
Published: (2020)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
by: Li, Xin, et al.
Published: (2024)

Perturbation-Resilient Trades for Dynamic Service Balancing
by: Sima, Jin, et al.
Published: (2024)

Unbounded Error Correcting Codes
by: Efremenko, Klim, et al.
Published: (2024)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

Trellis codes with a good distance profile constructed from expander graphs
by: Zhu, Yubin, et al.
Published: (2026)

Sparse Submodular Function Minimization
by: Graur, Andrei, et al.
Published: (2023)

Submodular Order Functions and Assortment Optimization
by: Udwani, Rajan
Published: (2021)

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
by: Chen, Li, et al.
Published: (2025)

Robust Online Sampling from Possibly Moving Target Distributions
by: Clément, François, et al.
Published: (2025)

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
by: Tate, Reuben, et al.
Published: (2024)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
by: Kar, Prem Nigam, et al.
Published: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
by: Diaby, Moustapha
Published: (2016)

Polyamorous Scheduling
by: Gąsieniec, Leszek, et al.
Published: (2024)