On Sublinear Algorithms of Reoptimization for Constraint Satisfaction Problems

被引：0

作者：

Mikhailyuk, V. A. ^{[1
]}

机构：

[1] Natl Acad Sci Ukraine, VM Glushkov Inst Cybernet, Kiev, Ukraine

来源：

JOURNAL OF AUTOMATION AND INFORMATION SCIENCES | 2013年 / 45卷 / 04期

关键词：

optimization algorithm; optimal approximation; approximation ratio; integrality gap; BOUNDED-DEGREE; APPROXIMATION; CSP; GRAPHS;

D O I：

10.1615/JAutomatInfScien.v45.i4.40

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

For solving Ins-Lambda-CSP (reoptimization of Lambda-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.

引用

页码：30 / 38

页数：9

共 12 条

[1] Reoptimizing the traveling salesman problem [J].

Archetti, C ;

Bertazzi, L ;

Speranza, MG .

NETWORKS, 2003, 42 (03) :154-159

[2]

Bogdanov A, 2002, ANN IEEE SYMP FOUND, P93, DOI 10.1109/SFCS.2002.1181886

[3]

Chi-Chih Yao A., 1977, 18th Annual Symposium on Foundations of Computer Science, P222

[4] Property testing and its connection to learning and approximation [J].

Goldreich, O ;

Goldwasser, S ;

Ron, D .

JOURNAL OF THE ACM, 1998, 45 (04) :653-750

[5]

KHOT S, 2002, STOC, P767

[6] The Price of Being Near-Sighted [J].

Kuhn, Fabian ;

Moscibroda, Thomas ;

Wattenhofer, Roger .

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :980-989

[7]

Marko S, 2006, LECT NOTES COMPUT SC, V4110, P475

[8]

Mikhailyuk V.A., 2012, KIBERNETIKA SISTEMNY, V47, P89

[9]

Parnas M., 2007, THEORET COMPUT SCI, V381, P183

[10]

Raghavendra P, 2008, ACM S THEORY COMPUT, P245

← 1 2 →