Geodesic
Local search methods for a column permutation problem for the binary matrix
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 12 (2012) no. 1, pp. 91-101
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The iterative local search methods for the column permutation problem for the binary matrix are developed and studied. It is known that the problem is NP-hard in the strong sense, and for the broad class of polynomial time approximation algorithms the relative deviation from the optimum may be arbitrary large in the worst case. In this paper we show that the iterative local search methods can find the global optimum or near optimal solution quickly if the number of columns and the number of rows of the matrix are 100 at most.
Keywords: local search, metaheuristic
Mots-clés : data compression. 
@article{VNGU_2012_12_1_a5,
     author = {Yu. A. Kochetov and M. G. Sivykh and A. V. Khmelev and A. V. Yakovlev},
     title = {Local search methods for a~column permutation problem for the binary matrix},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {91--101},
     year = {2012},
     volume = {12},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2012_12_1_a5/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
AU  - M. G. Sivykh
AU  - A. V. Khmelev
AU  - A. V. Yakovlev
TI  - Local search methods for a column permutation problem for the binary matrix
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2012
SP  - 91
EP  - 101
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VNGU_2012_12_1_a5/
LA  - ru
ID  - VNGU_2012_12_1_a5
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%A M. G. Sivykh
%A A. V. Khmelev
%A A. V. Yakovlev
%T Local search methods for a column permutation problem for the binary matrix
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2012
%P 91-101
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/VNGU_2012_12_1_a5/
%G ru
%F VNGU_2012_12_1_a5
Yu. A. Kochetov; M. G. Sivykh; A. V. Khmelev; A. V. Yakovlev. Local search methods for a column permutation problem for the binary matrix. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 12 (2012) no. 1, pp. 91-101. http://geodesic.mathdoc.fr/item/VNGU_2012_12_1_a5/

[1] Veldhorst M., “Approximation of the Consecutive Ones Matrix Augmentation Problem”, SIAM J. Comp., 14 (1985), 709–729 | DOI | MR | Zbl

[2] Booth K. S., Lueker G. S., “Testing for the Consecutive Ones Property, Interval Graphs and Graph Planarity Using PQ-Tree Algorithm”, J. Comput. System. Sci., 13 (1976), 335–379 | DOI | MR | Zbl

[3] Booth K. S., PQ-Tree Algorithms, Ph. D. Thesis, Univ. of California, Berkeley, 1975

[4] Cheng T. C. E., Diamond J. E., Lin B. M. T., “Optimal Scheduling in Film Production to Minimize Talent Hold Cost”, J. of Optim. Theory and Appl., 79:3 (1993), 479–492 | DOI | MR | Zbl

[5] Kononova P. A., Kochetov Yu. A., “Ob odnoi zadache vybora posledovatelnosti stolbtsov 0–1 matritsy”, Tr. 14-i Baikalskoi mezhdunarodnoi shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 1, Irkutsk, 2008, 444–451

[6] Nordström A. L., Tufekci S., “A Genetic Algorithm for the Talent Scheduling Problem”, Computers and Oper. Res., 21 (1994), 927–940 | DOI

[7] Aarts E. H. L., Korst J. H. M., Laarhoven van P. J. M., “Simulated Annealing”, Local Search in Combinatorial Optimization, Wiley, Chichester, 1997, 91–120 | MR | Zbl

[8] Glover F., Laguna M., Tabu Search, Kluwer Acad. Publ., Boston, 1997 | MR | Zbl

[9] Goncharov E. N., Kochetov Yu. A., “Veroyatnostnyi poisk s zapretami dlya diskretnykh zadach bezuslovnoi optimizatsii”, Diskret. analiz i issled. operatsii. Ser. 2, 9:2 (2002), 13–30 | MR | Zbl

[10] Kirkpatrick S., Gelatt C. D., Vecchi M. P., “Optimization by Simulated Annealing”, Science, 220 (1983), 671–680 | DOI | MR | Zbl

[11] Hansen P., Mladenović N., “Developments of Variable Neighborhood Search”, Essays and Surveys of Metaheuristics, Kluwer Acad. Publ., Boston, 2002, 415–440 | DOI | MR

[12] Rastrigin L. A., “Sluchainyi poisk – spetsifika, etapy istorii i predrassudki”, Voprosy kibernetiki, 33, 1978, 3–16

[13] Bremermann H. J., Roghson J., Salaff S., “Global Properties of Evolution Processes”, Natural Automata and Useful Simulations, Macmillan, L., 1966, 3–42

[14] Holland J. H., Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, 1975 | MR

[15] Goldberg D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989 | Zbl

[16] Lučić P., Teodorović D., “Computing with Bees: Attacking Complex Transportation Engineering Problems”, Intern. J. Artif. Intel. Tools, 12 (2003), 375–394 | DOI

[17] De la Banda M. G., Stuckey P. J., Chu G., “Solving Talent Scheduling with Dynamic Programming”, INFORMS J. Computing, 23:1 (2011), 120–137 | DOI | MR | Zbl