Probabilistic analysis of algorithms for discrete optimization problems is the subject of many recent investigations (Karp, Frieze, Radhavan at al). Probability inequalities of well known researchers (Chernov, Hoefding at al) are widely exploited in this works. The paper aims at demonstrating some results of probabilistic analysis of algorithms for a number of well known combinatorial problems that use another efficient (productive) probability inequalities (of Bernstein, Borovkov, Petrov, etc.). The results deal with proofs of asymptotical optimality of polynomial approximation algorithms for solving the traveling salesman problem, the bin packing problem, the multi-index assignment problem, the uncapacitated facility location problem, the problem of finding the regular connected subgraph of maximum weight.
展开▼
