Geodesic
Genetic local search the graph partitioning problem under cardinality constraints
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 1, pp. 164-176

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

For the graph partitioning problem under cardinality constraints, a genetic local search method is developed. At each iteration of the method, there is a set of local optima of the problem. This set is used to search for new local optima with a smaller error. The local search problem with certain polynomially searchable neighborhoods is proved to be tight PLS-complete. It is shown that, in the worst case, number of local improvements can be exponentially large for any pivoting rule. Numerical experiments are performed in the special case of edge weights equal to unity, when local search is a polynomial-time procedure. The results of the experiments indicate that the method is highly efficient and can be applied to large-scale problems. 
@article{ZVMMF_2012_52_1_a15,
     author = {Yu. A. Kochetov and A. V. Plyasunov},
     title = {Genetic local search the graph partitioning problem under cardinality constraints},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {164--176},
     publisher = {mathdoc},
     volume = {52},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a15/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
AU  - A. V. Plyasunov
TI  - Genetic local search the graph partitioning problem under cardinality constraints
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2012
SP  - 164
EP  - 176
VL  - 52
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a15/
LA  - ru
ID  - ZVMMF_2012_52_1_a15
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%A A. V. Plyasunov
%T Genetic local search the graph partitioning problem under cardinality constraints
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2012
%P 164-176
%V 52
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a15/
%G ru
%F ZVMMF_2012_52_1_a15
Yu. A. Kochetov; A. V. Plyasunov. Genetic local search the graph partitioning problem under cardinality constraints. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 1, pp. 164-176. http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a15/