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 条
  • [41] Generalized k-multiway cut problems
    Liu J.
    Peng Y.
    Zhao C.
    Journal of Applied Mathematics and Computing, 2006, 21 (1-2) : 69 - 82
  • [42] Fixed point theorems in generalized partially ordered G-metric spaces
    Saadati, R.
    Vaezpour, S. M.
    Vetro, P.
    Rhoades, B. E.
    MATHEMATICAL AND COMPUTER MODELLING, 2010, 52 (5-6) : 797 - 801
  • [43] Sampling Lovasz local lemma for general constraint satisfaction solutions in near-linear time
    He, Kun
    Wang, Chunyang
    Yin, Yitong
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 147 - 158
  • [44] A NONCONFORMING GENERALIZED FINITE ELEMENT METHOD FOR TRANSMISSION PROBLEMS
    Mazzucato, Anna L.
    Nistor, Victor
    Qu, Qingqin
    SIAM JOURNAL ON NUMERICAL ANALYSIS, 2013, 51 (01) : 555 - 576
  • [45] An iterative constraint energy minimizing generalized multiscale finite element method for contact problem
    Li, Zishang
    Ye, Changqing
    Chung, Eric T.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2025, 461
  • [46] Generalized Solutions of Quasi-Variational-Like Problems
    Bao, Truong Q.
    Hebestreit, Niklas
    Tammer, Christiane
    VIETNAM JOURNAL OF MATHEMATICS, 2020, 48 (03) : 509 - 526
  • [47] Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
    Yu, Chung-Kai
    van der Schaar, Mihaela
    Sayed, Ali H.
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2017, 65 (15) : 3893 - 3908
  • [48] On del**-distance and fixed point theorems in generalized partially ordered D*-metric spaces
    AL Jumaili, Alaa Mahmood
    Yang, Xiao Song
    JOURNAL OF NONLINEAR SCIENCES AND APPLICATIONS, 2015, 8 (01): : 46 - 54
  • [49] Superconvergence of triangular mixed finite elements for optimal control problems with an integral constraint
    Zhou, Jianwei
    Chen, Yanping
    Dai, Yongquan
    APPLIED MATHEMATICS AND COMPUTATION, 2010, 217 (05) : 2057 - 2066
  • [50] Exact-to-precision generalized perturbation theory for eigenvalue problems
    Wang, Congjian
    Abdel-Khalik, Hany S.
    NUCLEAR ENGINEERING AND DESIGN, 2013, 256 : 130 - 140
12345