IMPROVING THE COMPLEXITIES OF APPROXIMATION ALGORITHMS FOR OPTIMIZATION PROBLEMS

Authors
KOVALYOV MY
Citation
My. Kovalyov, IMPROVING THE COMPLEXITIES OF APPROXIMATION ALGORITHMS FOR OPTIMIZATION PROBLEMS, Operations research letters, 17(2), 1995, pp. 85-87
Citations number
10
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
17
Issue
2
Year of publication
1995
Pages
85 - 87
Database
ISI
SICI code
0167-6377(1995)17:2<85:ITCOAA>2.0.ZU;2-Y
Abstract
A procedure to improve the lower and upper bound for the optimal objec tive function value of a minimization problem is presented. The proced ure is based on an approximation scheme. Properties of this approximat ion scheme are established on which the correctness and effectiveness of the bound improvement procedure are based. The procedure is applied to improve the computational complexities of approximation algorithms for several single and parallel machine scheduling problems.