Probabilistic analysis. (English) Zbl 0588.90062
Combinatorial optimization, Annot. Bibliogr., Summer Sch. Dublin 1983, 52-88 (1985).
[For the entire collection see Zbl 0547.00052.]
This bibliography concentrates on three types of probabilistic analyses in combinatorial optimization: running time analysis, error analysis and value analysis. Review results are given on problems of finding matchings in graphs, stable sets, colorings, Hamiltonian cycles in random graphs, optimal assignments, shortest traveling salesman tours, location and routing problems in Euclidean space, surveys on the average behavior of variants of the simplex method for linear programming. Results on non- Euclidean packing and covering problems are collected. Finally, branch- and-bound and search techniques for solving hard problems are discussed.
This bibliography concentrates on three types of probabilistic analyses in combinatorial optimization: running time analysis, error analysis and value analysis. Review results are given on problems of finding matchings in graphs, stable sets, colorings, Hamiltonian cycles in random graphs, optimal assignments, shortest traveling salesman tours, location and routing problems in Euclidean space, surveys on the average behavior of variants of the simplex method for linear programming. Results on non- Euclidean packing and covering problems are collected. Finally, branch- and-bound and search techniques for solving hard problems are discussed.
Reviewer: H.T.Lau
MSC:
90C10 | Integer programming |
90C35 | Programming involving graphs or networks |
90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
05C35 | Extremal problems in graph theory |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
90B10 | Deterministic network models in operations research |
90B05 | Inventory, storage, reservoirs |
90C05 | Linear programming |
90C20 | Quadratic programming |