Mathematics of Operations Research

最新文章

• 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...
• ON SOME NETWORK FLOW GAMES AI翻译
  作者：GRANOT, D; GRANOT, F
  摘要：We analyze three subclasses of cooperative games arising from network optimization problems in which the resources, such as arcs or nodes in the network, are controlled by individuals who have conflicting objectives. The first subclass of cooperative games is induced by network optimization problems over directed augmented trees. We show that for this subclass of games the kernel coincides with the nucleolus, and that the nucleolus can be characterized as the unique revenue allocation vector i...
• A PROBABILISTIC APPROACH TO THE GENERALIZED HESSIAN AI翻译
  作者：HAUSSMANN, UG
  摘要：The quadratic variation of Brownian motion is used to give a new definition of a generalized Hessian for nonsmooth functions, totally independently of any gradients. A calculus is developed for the generalized Hessian of functions whose gradient is Lipschitz. It is also shown that for convex functions the Hessian is nonempty.
• ON STATIONARY STRATEGIES IN BOREL DYNAMIC-PROGRAMMING AI翻译
  作者：FEINBERG, EA
  作者单位：Yale University
  摘要：We consider a discrete time Markov decision model with Borel state and action spaces. It is proved that the supremum of the expected total rewards under all randomized stationary strategies is equal to the supremum of these rewards under all (nonrandomized) stationary strategies.
• STRONG APPROXIMATIONS OF OPEN QUEUING-NETWORKS AI翻译
  作者：HORVATH, L
  摘要：We consider a queueing system with one or more stations. We show that the queue length processes can be approximated with Brownian motions or reflected Brownian motions. Using the approximations we obtain rates of convergence of the distributions and expected values of queue lengths.