Local elimination algorithms for solving sparse discrete problems

O. A. Shcherbina

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 1, pp. 159-175

Résumé

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.

Bibliographie

[1] Zhuravlev Yu. I., Izbrannye nauchnye trudy, Magistr, M., 1998

[2] Zhuravlev Yu. I., Losev G. F., “Okrestnosti v zadachakh diskretnoi matematiki”, Kibernetika i sistemnyi analiz, 1995, no. 2, 32–41 | MR | Zbl

[3] Sergienko I. V., Shilo V. P., Zadachi diskretnoi optimizatsii: problemy, metody resheniya, issledovaniya, Nauk. dumka, Kiev, 2003

[4] Dechter R., “Bucket elimination: A unifying framework for reasoning”, Artificial Intelligence, 113 (1999), 41–85 | DOI | MR | Zbl

[5] Neapolitan R. E., Probabilistic reasoning in expert systems, Wiley, New York, 1990 | MR

[6] Pearl J., Probabilistic reasoning in intelligent systems, Morgan Kaufmann, San Mateo, 1998

[7] Beeri C., F agin R., Maier D., Yannakakis M., “On the desirability of acyclic database schemes”, J. ACM, 30 (1983), 479–513 | DOI | MR | Zbl

[8] Rose D. J., “A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations”, Graph Theory and Computing, Acad. Press, New York, 1972, 183–217 | MR

[9] Supply chain optimization: product/process design, facilities location and flow control, XVI, Ser. Appl. Optimizat., 94, Springer, New York, 2005

[10] Cook S. A., “The complexity of theorem-proving procedures”, Proc. 3rd Ann. ACM Symp. on Theory Comput. Mach., New York, 1971, 151–158 | Zbl

[11] Lauritzen S. L., Spiegelhalter D. J., “Local computations with probabilities on graphical structures and their application to expert systems”, J. Roy. Statist. Soc. Ser. B, 50 (1988), 205–247 | MR

[12] Golumbic M. C., Algorithmic graph theory and perfect graphs, Acad. Press, New York, 1980 | MR

[13] Courcelle B., “Graph rewriting: An algebraic and logic approach”, Handbook Theor. Comput. Sci., v. B, Elsevier, 1990, 193–242 | MR | Zbl

[14] Arnborg S., Corneil D. G., Proskurowski A., “A complexity of finding embedding in a $k$-tree”, SIAM J. Alg. Disc. Meth., 8 (1987), 277–284 | DOI | MR | Zbl

[15] Scherbina O. A., “O lokalnykh algoritmakh resheniya kvaziblochnykh zadach diskretnogo programmirovaniya”, Probl. kibernetiki, 40, Nauka, M., 1983, 171–200

[16] Scherbina O. A., “Lokalnye algoritmy dlya blochno-drevovidnykh zadach diskretnogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 25:8 (1985), 1143–1154 | MR

[17] Scherbina O.A., “O neserialnoi modifikatsii lokalnogo algoritma dekompozitsii zadach diskretnoi optimizatsii”, Dinamich. sistemy, 19, 2005, 179–190

[18] Scherbina O. A., “Eliminatsionnye algoritmy dekompozitsii zadach diskretnoi optimizatsii”, Tavrich. vestn. informatiki i matem., 2006, no. 2, 28–41

[19] Scherbina O. A., “Lokalnye algoritmy i drevovidnaya dekompozitsiya dlya zadach diskretnoi optimizatsii”, Dinamich. sistemy, 20, 2006, 89–103

[20] Bertele U., Brioschi F., Nonserial dynamic programming, Acad. Press, New York, 1972 | MR | Zbl

[21] Harary F., Norman R. Z., Cartwright D., Structural models: An introduction to the theory of directed graphs, John Wiley Sons, New York, 1965 | MR | Zbl

[22] Amestoy P. R., Davis T. A., Duff I. S., “An approximate minimum degree ordering algorithm”, SIAM J. Matrix Analys. and Appl., 17:4 (1996), 886–905 | DOI | MR | Zbl

[23] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[24] Heggernes P., “Minimal triangulations of graphs: A survey”, Discrete Math., 305:3 (2006), 297–317 | DOI | MR

[25] Evstigneev V. A., Kasyanov V. H., Tolkovyi slovar po teorii grafov v informatike i programmirovanii, Nauka, Novosibirsk, 1999 http://pco.iis.nsk.su/grap | Zbl

[26] Parter S., “The use of linear graphs in Gauss elimination”, SIAM Rev., 3 (1961), 119–130 | DOI | MR | Zbl

[27] Fulkerson D. R., Gross O. A., “Incidence matrices and interval graphs”, Pacific J. Math., 15 (1965), 835–855 | MR | Zbl

[28] Yannakakis M., “Computing the minimum full-in is NP-complete”, SIAM J. Alg. Disc. Meth., 2 (1981), 77–79 | DOI | MR | Zbl

[29] Robertson N., Seymour P., “Graph minors II. Algorithmic aspects of treewidth”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[30] Bodlaender H. L., “Discovering treewidth”, Proc. SOFSEM, LNCS, 3381, Springer, Berlin etc., 2006, 1–16 | MR

[31] Dechter R., El Fattah Y., “Topological parameters for time-space tradeoff”, Artificial Intelligence, 125:1–2 (2001), 93–118 | DOI | MR | Zbl

[32] Heggernes P., Treewidth, partial $k$-trees, and chordal graphs http://www.ii.uib.no/~pinar/chordal.pdf

[33] Dirac G. A., “On rigid circuit graphs”, Ann. Math. Sem. Hamburg, 25, Hamburg, 1961, 71–76 | MR | Zbl

[34] Bernstein P. A., Goodman N., “Power of natural semijoints”, SIAM J. Comput., 10:4 (1981), 751–771 | DOI | MR | Zbl

[35] Scherbina O. A., “Lokalnye eliminatsionnye algoritmy dlya zadach udovletvoreniya ogranichenii”, Tavrich. vestn. informatiki i matem., 2007, no. 1, 24–39

[36] Scherbina O. A., “Drevovidnaya dekompozitsiya i zadachi diskretnoi optimizatsii (obzor)”, Kibernetika i sistemnyi analiz, 2007, no. 4, 102–118