EUVIMEDEUVIMED entdecken
Crossref

Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs

Henrique Assumpção, Gabriel Coutinho

Mathematics of Operations Research · 04.06.2026

DOI: 10.1287/moor.2025.1044 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 04.06.2026. Verfasst von Henrique Assumpção und 1 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We use semidefinite programming to bound the fractional cut-cover parameter of graphs in association schemes in terms of their smallest eigenvalue. We also extend the equality cases of a primal-dual inequality involving the Goemans-Williamson semidefinite program, which approximates maxcut, to graphs in certain coherent configurations. Moreover, we obtain spectral bounds for max 2-sat when the underlying graphs belong to an association scheme by means of a certain semidefinite program used to approximate quadratic programs, and we further develop this technique in order to explicitly compute the optimum value of its gauge dual in the case of distance-regular graphs. Funding: This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico and Fundação de Amparo à Pesquisa do Estado de Minas Gerais.

Zitieren

APA

Assumpção, H., & Coutinho, G. (2026). Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs. Mathematics of Operations Research. https://doi.org/10.1287/moor.2025.1044

Vancouver

Assumpção H, Coutinho G. Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs. Mathematics of Operations Research. 2026. doi:10.1287/moor.2025.1044

BibTeX
@article{Assumpo2026,
  author = {Assumpção, Henrique and Coutinho, Gabriel},
  title = {Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs},
  journal = {Mathematics of Operations Research},
  year = {2026},
  doi = {10.1287/moor.2025.1044}
}
Kostenlos starten →