Geodesic
Piecewise convex formulations of binary and permutation problems
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 14 (2011) no. 4, pp. 409-423

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

It is well-known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem. 
@article{SJVM_2011_14_4_a5,
     author = {D. Fortin and I. Tseveendorj},
     title = {Piecewise convex formulations of binary and permutation problems},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {409--423},
     publisher = {mathdoc},
     volume = {14},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/}
}
TY  - JOUR
AU  - D. Fortin
AU  - I. Tseveendorj
TI  - Piecewise convex formulations of binary and permutation problems
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2011
SP  - 409
EP  - 423
VL  - 14
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/
LA  - ru
ID  - SJVM_2011_14_4_a5
ER  - 
%0 Journal Article
%A D. Fortin
%A I. Tseveendorj
%T Piecewise convex formulations of binary and permutation problems
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2011
%P 409-423
%V 14
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/
%G ru
%F SJVM_2011_14_4_a5
D. Fortin; I. Tseveendorj. Piecewise convex formulations of binary and permutation problems. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 14 (2011) no. 4, pp. 409-423. http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/