Optimal Approximate Algorithm for Reoptimization of Strict Constraint Satisfaction Problems

被引：0
作者：
Mikhailyuk, V. A. [1 ]
机构：
[1] Natl Acad Sci Ukraine, VM Glushkov Cybernet Inst, Kiev, Ukraine
来源：
JOURNAL OF AUTOMATION AND INFORMATION SCIENCES | 2012年 / 44卷 / 11期
关键词：
optimal approximate algorithm; approximation ratio; integrality gap on l inear relaxation; hierarchy of relaxation; unique game problem; RELAXATIONS; HARDNESS;
D O I：
10.1615/JAutomatInfScien.v44.i11.40
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
With the unique games conjecture (UGC) held there exists the optimal approximate algorithm for reoptimization of strict constraint satisfaction problems (under insertion of any constraint). The approximation ratio of this algorithm depends on the integrality gap on linear relaxation of the original problem.
引用
收藏
页码：45 / 54
页数：10
相关论文
共 12 条
  • [1] Reoptimization of Ordered Generalized Constraint Satisfaction Problems
    Mikhailyuk, V. A.
    JOURNAL OF AUTOMATION AND INFORMATION SCIENCES, 2012, 44 (06) : 61 - 70
  • [2] On Sublinear Algorithms of Reoptimization for Constraint Satisfaction Problems
    Mikhailyuk, V. A.
    JOURNAL OF AUTOMATION AND INFORMATION SCIENCES, 2013, 45 (04) : 30 - 38
  • [3] Simultaneous Approximation of Constraint Satisfaction Problems
    Bhangale, Amey
    Kopparty, Swastik
    Sachdeva, Sushant
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 193 - 205
  • [4] BINARISATION FOR VALUED CONSTRAINT SATISFACTION PROBLEMS
    Cohen, David A.
    Cooper, Martin C.
    Jeavons, Peter G.
    Krokhin, Andrei
    Powell, Robert
    Zivny, Stanislav
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (04) : 2279 - 2300
  • [5] Local consistency as a reduction between constraint satisfaction problems
    Dalmau, Victor
    Oprsal, Jakub
    PROCEEDINGS OF THE 39TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS 2024, 2024,
  • [6] Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps
    Barto, Libor
    FUNDAMENTALS OF COMPUTATION THEORY, FCT 2019, 2019, 11651 : 3 - 17
  • [7] Approximate Techniques in Solving Optimal Camera Placement Problems
    Zhao, Jian
    Yoshida, Ruriko
    Cheung, Sen-ching Samson
    Haws, David
    INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS, 2013,
  • [8] Approximate techniques in solving optimal camera placement problems
    Zhao, Jian
    Haws, David
    Yoshida, Ruriko
    Cheung, Sen-ching Samson
    2011 IEEE INTERNATIONAL CONFERENCE ON COMPUTER VISION WORKSHOPS (ICCV WORKSHOPS), 2011,
  • [9] From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
    Ghosh, Mrinalkanti
    Tulsiani, Madhur
    THEORY OF COMPUTING, 2018, 14
  • [10] THE COMPLEXITY OF GENERAL-VALUED CONSTRAINT SATISFACTION PROBLEMS SEEN FROM THE OTHER SIDE
    Carbonnel, Clement
    Romero, Miguel
    Zivny, Stanislav
    SIAM JOURNAL ON COMPUTING, 2022, 51 (01) : 19 - 69
12