1993

最新文章

• ANALYSIS OF PROBABILISTIC COMBINATORIAL OPTIMIZATION PROBLEMS IN EUCLIDEAN SPACES AI翻译
  作者：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...
• SENSORS AND INFORMATION IN OPTIMIZATION UNDER STOCHASTIC UNCERTAINTY AI翻译
  作者：ARTSTEIN, Z; WETS, RJB
  作者单位：University of California System; University of California Davis
  摘要：The paper offers a framework for the analysis of information available in stochastic optimization problems. The setup proposed here applies to the situation where the decision maker can seek more information about the stochastics of the problem. The information collected in the inquiry only allows for a redefinition of the distribution of the stochastic elements, and the inquiry process itself may introduce new errors and uncertainties. The tool we introduce is termed sensor. Compared with pre...
• OPTIMAL STOPPING BY MEANS OF POINT PROCESS OBSERVATIONS WITH APPLICATIONS IN RELIABILITY AI翻译
  作者：JENSEN, U; HSU, GH
  作者单位：Chinese Academy of Sciences
  摘要：A problem in reliability is considered in which only partial information is available. Some technical system is assumed to work in one of N unobservable states. The changes of the states are driven by a Markov process with known characteristics. The system fails from time to time according to a point process with a failure rate (intensity) which depends on the unobservable state. After failure a minimal repair is carried out immediately which leaves the state of the system unchanged. It is inv...
• THE TRAVELING SALESMAN PROBLEM WITH DISTANCES ONE AND 2 AI翻译
  作者：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.
• THE COMPLEXITY OF ELIMINATING DOMINATED STRATEGIES AI翻译
  作者：GILBOA, I; KALAI, E; ZEMEL, E
  摘要：This paper deals with the computational complexity of some yes/no problems associated with sequential elimination of strategies using three domination relations: strong domination (strict inequalities), weak domination (weak inequalities), and domination (the asymmetric part of weak domination). Classification of various problems as polynomial or NP-complete seems to suggest that strong domination is a simple notion, whereas weak domination and domination are complicated ones.
• PROBABILISTIC ANALYSIS OF NETWORK FLOW ALGORITHMS AI翻译
  作者：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...