-
作者：JAILLET, P
作者单位：University of Texas System; University of Texas Austin
摘要：Probabilistic combinatorial optimization problems are generalized versions of deterministic combinatorial optimization problems with explicit inclusion of probabilistic elements in the problem definitions. Based on the probabilistic traveling salesman problem (PTSP) and on the probabilistic minimum spanning tree problem (PMSTP), the objective of this paper is to give a rigorous treatment of the probabilistic analysis of these problems in the plane. More specifically we present general finite-s...
-
作者：PAPADIMITRIOU, CH; YANNAKAKIS, M
作者单位：Nokia Corporation; Nokia Bell Labs; AT&T
摘要：We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.
-
作者：KARP, RM; MOTWANI, R; NISAN, N
作者单位：Stanford University; Hebrew University of Jerusalem
摘要：This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data are determinist...
