Semidefinite Programming and Linear Equations vs. Homomorphism Problems

被引：0
作者：
Ciardo, Lorenzo [1 ]
Zivny, Stanislav [1 ]
机构：
[1] Univ Oxford, Oxford, England
来源：
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024 | 2024年
关键词：
approximate graph colouring; approximate graph homomorphism; semidefinite programming relaxations; affine integer programming relaxations; Diophantine equations; promise constraint satisfaction; CONSTRAINT SATISFACTION; ASSOCIATION SCHEMES; ALGEBRAIC STRUCTURE; CHROMATIC NUMBER; SHERALI-ADAMS; COMPLEXITY; HARDNESS; POWER; RELAXATIONS; SYMMETRY;
D O I：
10.1145/3618260.3649635
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations, and propose a framework for the analysis of its power based on the spectral theory of association schemes. We use this framework to establish an unconditional lower bound against the semidefinite programming + linear equations model, by showing that the relaxation does not solve the approximate graph homomorphism problem and thus, in particular, the approximate graph colouring problem.
引用
收藏
页码：1935 / 1943
页数：9
相关论文
共 46 条
  • [1] Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
    Fiorini, Samuel
    Massar, Serge
    Pokutta, Sebastian
    Tiwary, Hans Raj
    de Wolf, Ronald
    STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 95 - 106
  • [2] Linear Index Coding via Semidefinite Programming
    Chlamtac, Eden
    Haviv, Ishay
    COMBINATORICS PROBABILITY & COMPUTING, 2014, 23 (02) : 223 - 247
  • [3] Semidefinite programming for min-max problems and games
    Laraki, R.
    Lasserre, J. B.
    MATHEMATICAL PROGRAMMING, 2012, 131 (1-2) : 305 - 332
  • [4] A Semidefinite Programming approach for solving Multiobjective Linear Programming
    Blanco, Victor
    Puerto, Justo
    Ben Ali, Safae El Haj
    JOURNAL OF GLOBAL OPTIMIZATION, 2014, 58 (03) : 465 - 480
  • [5] On linear and semidefinite programming relaxations for hypergraph matching
    Chan, Yuk Hei
    Lau, Lap Chi
    MATHEMATICAL PROGRAMMING, 2012, 135 (1-2) : 123 - 148
  • [6] SEMIDEFINITE PROGRAMMING RELAXATIONS FOR LINEAR SEMI-INFINITE POLYNOMIAL PROGRAMMING
    Guo, Feng
    Sun, Xiaoxia
    PACIFIC JOURNAL OF OPTIMIZATION, 2020, 16 (03): : 395 - 418
  • [7] Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines
    Kurpisz, Adam
    Mastrolilli, Monaldo
    Mathieu, Claire
    Moemke, Tobias
    Verdugo, Victor
    Wiese, Andreas
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2016, 2016, 9682 : 152 - 163
  • [8] Semidefinite and linear programming integrality gaps for scheduling identical machines
    Kurpisz, Adam
    Mastrolilli, Monaldo
    Mathieu, Claire
    Moemke, Tobias
    Verdugo, Victor
    Wiese, Andreas
    MATHEMATICAL PROGRAMMING, 2018, 172 (1-2) : 231 - 248
  • [9] A semidefinite programming approach for stochastic switched optimal control problems
    Davoudi, Ramtin
    Hosseini, Seyed Mohammad
    Ramezani, Amin
    2019 IEEE 58TH CONFERENCE ON DECISION AND CONTROL (CDC), 2019, : 2503 - 2508
  • [10] Semidefinite programming relaxations for graph coloring and maximal clique problems
    Igor Dukanovic
    Franz Rendl
    Mathematical Programming, 2007, 109 : 345 - 365
12345