Reoptimization of Ordered Generalized 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卷 / 06期
关键词：
unique games conjecture; solving the Ins-OCSP problem; reoptimization; polynomial optimal (threshold) approximate algorithm; approximation ratio; INAPPROXIMABILITY; APPROXIMATION; HARDNESS;
D O I：
10.1615/JAutomatInfScien.v44.i6.60
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
While the truth of the unique games conjecture (UGC), for solving the Ins-OCSP problem (OCSP reoptimization, when adding a single constraint), there exists a polynomial optimal (threshold) approximate algorithm. Its approximation ratio depends on the threshold "random" approximation ratio for solving the OCSP problem.
引用
收藏
页码：61 / 70
页数：10
相关论文
共 50 条
  • [1] On Sublinear Algorithms of Reoptimization for Constraint Satisfaction Problems
    Mikhailyuk, V. A.
    JOURNAL OF AUTOMATION AND INFORMATION SCIENCES, 2013, 45 (04) : 30 - 38
  • [2] Optimal Approximate Algorithm for Reoptimization of Strict Constraint Satisfaction Problems
    Mikhailyuk, V. A.
    JOURNAL OF AUTOMATION AND INFORMATION SCIENCES, 2012, 44 (11) : 45 - 54
  • [3] REOPTIMIZATION OF CONSTRAINT SATISFACTION PROBLEMS WITH APPROXIMATION RESISTANT PREDICATES
    Mikhailyuka, V. A.
    Sergienko, I. V.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2012, 48 (01) : 73 - 85
  • [4] Reoptimization of constraint satisfaction problems with approximation resistant predicates
    V. A. Mikhailyuk
    I. V. Sergienko
    Cybernetics and Systems Analysis, 2012, 48 (1) : 73 - 85
  • [5] Reoptimization of maximum weight induced hereditary subgraph problems
    Boria, Nicolas
    Monnot, Jerome
    Paschos, Vangelis Th
    THEORETICAL COMPUTER SCIENCE, 2013, 514 : 61 - 74
  • [6] ROBUSTLY SOLVABLE CONSTRAINT SATISFACTION PROBLEMS
    Barto, Libor
    Kozik, Marcin
    SIAM JOURNAL ON COMPUTING, 2016, 45 (04) : 1646 - 1669
  • [7] Simultaneous Approximation of Constraint Satisfaction Problems
    Bhangale, Amey
    Kopparty, Swastik
    Sachdeva, Sushant
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 193 - 205
  • [8] Robust Satisfiability of Constraint Satisfaction Problems
    Barto, Libor
    Kozik, Marcin
    STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 931 - 940
  • [9] Reoptimization of set covering problems
    Mikhailyuk V.A.
    Cybernetics and Systems Analysis, 2010, 46 (6) : 879 - 883
  • [10] Heuristic reoptimization of time-extended multi-robot task allocation problems
    Bischoff, Esther
    Kohn, Saskia
    Hahn, Daniela
    Braun, Christian
    Rothfuss, Simon
    Hohmann, Soeren
    NETWORKS, 2024, 84 (01) : 64 - 83
12345