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 条
  • [31] Property testers for dense constraint satisfaction programs on finite domains
    Andersson, G
    Engebretsen, L
    RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (01) : 14 - 32
  • [32] MONOTONE GENERALIZED WEAK CONTRACTIONS IN PARTIALLY ORDERED METRIC SPACES
    Saadati, R.
    Vaezpour, S. M.
    FIXED POINT THEORY, 2010, 11 (02): : 375 - 382
  • [33] The nearness problems for symmetric centrosymmetric with a special submatrix constraint
    Li, Jiao-Fen
    Hu, Xi-Yan
    Zhang, Lei
    NUMERICAL ALGORITHMS, 2010, 55 (01) : 39 - 57
  • [34] A fixed point theorem in generalized ordered metric spaces with application
    Gholizadeh, Leila
    JOURNAL OF NONLINEAR SCIENCES AND APPLICATIONS, 2013, 6 (04): : 244 - 251
  • [35] Monotone generalized contractions in partially ordered probabilistic metric spaces
    Ciric, Lj. B.
    Mihet, D.
    Saadati, R.
    TOPOLOGY AND ITS APPLICATIONS, 2009, 156 (17) : 2838 - 2844
  • [36] Constraint-aware neural networks for Riemann problems
    Magiera, Jim
    Ray, Deep
    Hesthaven, Jan S.
    Rohde, Christian
    JOURNAL OF COMPUTATIONAL PHYSICS, 2020, 409
  • [37] Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games
    Caragiannis, Ioannis
    Fanelli, Angelo
    Gravin, Nick
    ALGORITHMIC GAME THEORY, SAGT 2014, 2014, 8768 : 49 - 60
  • [38] Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games
    Caragiannis, Ioannis
    Fanelli, Angelo
    Gravin, Nick
    ALGORITHMICA, 2017, 77 (04) : 1143 - 1158
  • [39] Contractive Mapping in Generalized, Ordered Metric Spaces with Application in Integral Equations
    Gholizadeh, L.
    Saadati, R.
    Shatanawi, W.
    Vaezpour, S. M.
    MATHEMATICAL PROBLEMS IN ENGINEERING, 2011, 2011
  • [40] Generalized Multitasking for Evolutionary Optimization of Expensive Problems
    Ding, Jinliang
    Yang, Cuie
    Jin, Yaochu
    Chai, Tianyou
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2019, 23 (01) : 44 - 58
12345