图书馆订阅: Guest
Begell Digital Portal Begell 数字图书馆 电子图书 期刊 参考文献及会议录 研究收集
自动化与信息科学期刊
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN 打印: 1064-2315
ISSN 在线: 2163-9337

卷:
卷 52, 2020 卷 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

自动化与信息科学期刊

DOI: 10.1615/JAutomatInfScien.v45.i4.40
pages 30-38

On Sublinear Algorithms of Reoptimization for Constraint Satisfaction Problems

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

ABSTRACT

For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) there exists an optimal approximation algorithm with additive error of constant complexity. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial 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
TWO-DIMENSIONAL BOUNDARY VALUE PROBLEM FOR SYMMETRIC EQUATION OF ANOMALOUS DIFFUSION
Computational Thermal Sciences: An International Journal, Vol.8, 2016, issue 1
Marina Synah, Dmytro Kushnir, Tetiana Kirichok
Optimization of Perfect Reconstruction Cosine-Modulated Filter Banks: Fast Algorithm
Telecommunications and Radio Engineering, Vol.56, 2001, issue 12
Yuriy V. Shkvarko, Rene Jaime-Rivas, Jose A. Andrade-Lucio, Oscar G. Ibarra-Manzano, Gordana Jovanovic-Dolecek
Reoptimization of Ordered Generalized Constraint Satisfaction Problems
Journal of Automation and Information Sciences, Vol.44, 2012, issue 6
Victor A. Mikhailyuk
Correction of Controls of Nonstationary Objects on the Basis of the Invariance Property of the Riccati Equation
Journal of Automation and Information Sciences, Vol.30, 1998, issue 2-3
Yuriy G. Bulychev, Igor V. Burlai