Доступ предоставлен для: Guest
Портал Begell Электронная Бибилиотека e-Книги Журналы Справочники и Сборники статей Коллекции
Journal of Automation and Information Sciences
SJR: 0.238 SNIP: 0.464 CiteScore™: 0.27

ISSN Печать: 1064-2315
ISSN Онлайн: 2163-9337

Выпуски:
Том 51, 2019 Том 50, 2018 Том 49, 2017 Том 48, 2016 Том 47, 2015 Том 46, 2014 Том 45, 2013 Том 44, 2012 Том 43, 2011 Том 42, 2010 Том 41, 2009 Том 40, 2008 Том 39, 2007 Том 38, 2006 Том 37, 2005 Том 36, 2004 Том 35, 2003 Том 34, 2002 Том 33, 2001 Том 32, 2000 Том 31, 1999 Том 30, 1998 Том 29, 1997 Том 28, 1996

Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v44.i6.60
pages 61-70

Reoptimization of Ordered Generalized Constraint Satisfaction Problems

Victor A. Mikhailyuk
V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kiev

Краткое описание

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.


Articles with similar content:

Optimal Approximate Algorithm for Reoptimization of Strict Constraint Satisfaction Problems
Journal of Automation and Information Sciences, Vol.44, 2012, issue 11
Victor A. Mikhailyuk
Synthesis of Compromise-Optimal Trajectories of Mobile Objects in Conflict Environment
Journal of Automation and Information Sciences, Vol.34, 2002, issue 2
Sergey A. Shvorov, Alexander G. Yasinsky, Albert N. Voronin
Determination of Optimal Routes of Single-Frame Shooting by Spacecrafts and Their Clusters
Journal of Automation and Information Sciences, Vol.47, 2015, issue 1
Vsevolod M. Kuntsevich
On Sublinear Algorithms of Reoptimization for Constraint Satisfaction Problems
Journal of Automation and Information Sciences, Vol.45, 2013, issue 4
Victor A. Mikhailyuk
Attainability Domains for Linear and Some Classes of Nonlinear Discrete Systems and Their Control
Journal of Automation and Information Sciences, Vol.42, 2010, issue 1
Alexander B. Kurzhanski, Vsevolod M. Kuntsevich