Geodesic
Computational bounds for local search in combinatorial optimization
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 788-807

Voir la notice de l'article provenant de la source Math-Net.Ru

The results related to finding local optima in combinatorial optimization are overviewed. The class of polynomial-time local search problems (class PLS) is considered. By analogy with Cook's theorem, the existence of most complicated problems in this class is established. The number of steps in local descent algorithms is estimated in the worst and average cases. The local search determination of exact and approximate solutions with guaranteed error bounds is discussed. 
@article{ZVMMF_2008_48_5_a4,
     author = {Yu. A. Kochetov},
     title = {Computational bounds for local search in combinatorial optimization},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {788--807},
     publisher = {mathdoc},
     volume = {48},
     number = {5},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a4/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
TI  - Computational bounds for local search in combinatorial optimization
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2008
SP  - 788
EP  - 807
VL  - 48
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a4/
LA  - ru
ID  - ZVMMF_2008_48_5_a4
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%T Computational bounds for local search in combinatorial optimization
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2008
%P 788-807
%V 48
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a4/
%G ru
%F ZVMMF_2008_48_5_a4
Yu. A. Kochetov. Computational bounds for local search in combinatorial optimization. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 788-807. http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a4/