-
作者：Kern, Walter; Paulusma, Daniel
作者单位：University of Twente; Durham University
摘要：Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124-131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2006. The nucleolus of balanced simple flow networks. Games Econom. Behav. 54 205-225] show that the nucleolus of simple flow games (where all edge capacities are equal to one) can be computed in polynomial time. Our main result is a combinatorial m...
-
作者：Baumann, Nadine; Skutella, Martin
作者单位：Dortmund University of Technology; Technical University of Berlin
摘要：Earliest arrival flows capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink as quickly as possible. The latter requirement is made more precise by the earliest arrival property, which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical ...
-
作者：Huh, Woonghee Tim; Janakiraman, Ganesh; Muckstadt, John A.; Rusmevichientong, Paat
作者单位：Columbia University; New York University; Cornell University
摘要：We consider a periodic-review, single-location, single-product inventory system with lost sales and positive replenishment lead times. It is well known that the optimal policy does not possess a simple structure. Motivated by recent results showing that base-stock policies perform well in these systems, we study the problem of finding the best base-stock policy in such a system. In contrast to the classical inventory literature, we assume that the manager does not know the demand distribution ...
-
作者：Zhang, Jiheng; Dai, J. G.; Zwart, Bert
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Motivated by applications in computer and communication systems, we consider a processor-sharing queue where the number of jobs served is not larger than K. We propose a measure-valued fluid model for this limited processor-sharing queue and show that there exists a unique associated fluid model solution. In addition, we show that this fluid model arises as the limit of a sequence of appropriately scaled processor-sharing queues.
-
作者：Miyazawa, Masakiyo
作者单位：Tokyo University of Science
摘要：A double quasi-birth-and-death (QBD) process is the QBD process whose background process is a homogeneous birth-and-death process, which is a synonym of a skip-free random walk in the two-dimensional positive quadrant with homogeneous reflecting transitions at each boundary face. It is also a special case of a 0-partially homogenous chain introduced by Borovkov and Mogul'skii. Our main interest is in the tail decay behavior of the stationary distribution of the double QBD process in the coordi...
-
作者：So, Anthony Man-Cho; Zhang, Jiawei; Ye, Yinyu
作者单位：Chinese University of Hong Kong; New York University; Stanford University
摘要：Most of the recent work on 2-stage stochastic combinatorial optimization problems has focused on minimization of the expected cost or the worst-case cost of the solution. Those two objectives can be viewed as two extreme ways of handling risk. In this paper we propose to use a one-parameter family of functionals to interpolate between them. Although such a family has been used in the mathematical finance and stochastic programming literature before, its use in the context of approximation algo...
-
作者：Hofbauer, Josef; Sorin, Sylvain; Viossat, Yannick
作者单位：University of Vienna; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique; Universite PSL; Universite Paris-Dauphine
摘要：Using an explicit representation in terms of the logit map, we show, in a unilateral framework, that the time average of the replicator dynamics is a perturbed solution of the best-reply dynamics.
