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 条
  • [21] Semilocal density functionals and constraint satisfaction
    Perdew, John P.
    Sun, Jianwei
    Martin, Richard M.
    Delley, Bernard
    INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2016, 116 (11) : 847 - 851
  • [22] TOPOLOGY AND ADJUNCTION IN PROMISE CONSTRAINT SATISFACTION\ast
    Krokhin, Andrei
    Oprsval, Jakub
    Wrochna, Marcin
    Zivny, Stanislav
    SIAM JOURNAL ON COMPUTING, 2023, 52 (01) : 38 - 79
  • [23] Approximate Constraint Satisfaction Requires Large LP Relaxations
    Chan, Siu On
    Lee, James R.
    Raghavendra, Prasad
    Steurer, David
    JOURNAL OF THE ACM, 2016, 63 (04)
  • [24] Balanced Random Constraint Satisfaction: Phase Transition and Hardness
    Liu, Tian
    Wang, Chaoyi
    Xu, Wei
    FRONTIERS IN ALGORITHMICS (FAW 2018), 2018, 10823 : 238 - 250
  • [25] Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
    Feng, Weiming
    He, Kun
    Yin, Yitong
    STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 1565 - 1578
  • [26] On the Ordered List Subgraph Embedding Problems
    Hassan, Olawale
    Kanj, Iyad
    Lokshtanov, Daniel
    Perkovic, Ljubomir
    ALGORITHMICA, 2016, 74 (03) : 992 - 1018
  • [27] On the Ordered List Subgraph Embedding Problems
    Olawale Hassan
    Iyad Kanj
    Daniel Lokshtanov
    Ljubomir Perković
    Algorithmica, 2016, 74 : 992 - 1018
  • [28] Strong intractability results for generalized convex recoloring problems
    Moura, Phablo F. S.
    Wakabayashi, Yoshiko
    DISCRETE APPLIED MATHEMATICS, 2020, 281 : 252 - 260
  • [29] Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy
    Brakensiek, Joshua
    Guruswami, Venkatesan
    SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1782 - 1801
  • [30] PROMISE CONSTRAINT SATISFACTION: ALGEBRAIC STRUCTURE AND A SYMMETRIC BOOLEAN DICHOTOMY
    Brakensiek, Joshua
    Guruswami, Venkatesan
    SIAM JOURNAL ON COMPUTING, 2021, 50 (06) : 1663 - 1700
12345