-
作者：MONTICINO, MG
摘要：Suppose measurability structures are imposed upon a Dubins and Savage gambling problem. A long-standing question asks whether strategies which are measurable with respect to these structures enable the gambler to maximize his return. Measurable strategies have the advantage over arbitrary strategies in that they induce countably additive probability measures. In this work, we show that measurable strategies are adequate in order to maximize return if and only if the optimal return function is ...
-
作者：TARJAN, RE
作者单位：Nokia Corporation; Nokia Bell Labs; AT&T
摘要：We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a bound of n(log n)/2 + O(1) on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in n(log n)/2 + O(1) time. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running tim...
-
作者：KOJIMA, M; MEGIDDO, N; NOMA, T
作者单位：International Business Machines (IBM); IBM USA; Tel Aviv University; Institute of Science Tokyo; Tokyo Institute of Technology
摘要：A complementarity problem with a continuous mapping f from R(n) into itself can be written as the system of equations F(x,y) = 0 and (x,y) greater-than-or-equal-to 0. Here F is the mapping from R2n into itself defined by F(x,y) = (x1y1, x2y2,...,x(n)y(n),y-f(x)). Under the assumption that the mapping f is a P0-function, we study various aspects of homotopy continuation methods that trace a trajectory consisting of solutions of the family of systems of equations F(x,y) = t(a,b) and (x,y) greate...
-
作者：GOLDBERG, AV; PLOTKIN, SA; TARDOS, E
作者单位：Stanford University; Cornell University
摘要：We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e)-gamma-(e) units arrive at the other end. For instance, nodes of the graph can correspond to different currencies, with the multipliers being the exchange rates. We require conservation of flow at every node except a given source node. The goal is to maximize the amount of flow excess at the source. Thi...
-
作者：PETERSON, WP
摘要：The central result of this paper is a heavy traffic limit theorem for the vector of total station workloads in an open network of queues with multiple customer types, under first-come-first-served and priority disciplines. The limit process is a regulated Brownian motion on the nonnegative orthant, with parameters specified from the first two moments of the interarrival and service time distributions and a matrix of reduced routing information. Through the phenomenon of state space collapse, a...
