-
作者：Galluccio, Anna; Gentile, Claudio; Ventura, Paolo
作者单位：Consiglio Nazionale delle Ricerche (CNR)
摘要：Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB (H) and STAB (H-e), where He is the graph obtained from H by subdividing the edge e. We also introduce the class of G-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-whee...
-
作者：Zadorojniy, Alexander; Even, Guy; Shwartz, Adam
作者单位：Tel Aviv University; Technion Israel Institute of Technology
摘要：We consider the problem of computing optimal policies of finite-state finite-action Markov decision processes (MDPs). A reduction to a continuum of constrained MDPs (CMDPs) is presented such that the optimal policies for these CMDPs constitute a path in a graph defined over the deterministic policies. This path contains, in particular, an optimal policy of the original MDP. We present an algorithm based on this new approach that finds this path, and thus an optimal policy. In the general case,...
-
作者：Randhawa, Ramandeep S.; Kumar, Sunil
作者单位：University of Texas System; University of Texas Austin; Stanford University
摘要：We study a multiserver loss system with two kinds of customers: subscribers and infrequent users. We model the infrequent users' requests for service by a Poisson process. However, noting that the Poisson process is unable to capture repeated interactions as well as retrials, we propose a Markovian on-off-hold model for the subscribers' requests for service that takes into account retrials by subscribers denied service. We analyze this system in an asymptotic regime where the number of subscri...
-
作者：Blanquero, Rafael; Carrizosa, Emilio; Hansen, Pierre
作者单位：University of Sevilla; Universite de Montreal; Universite de Montreal; HEC Montreal
摘要：We address the problem of locating objects in the plane such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries. Given a set of points, we seek the rotation and translation for such an object optimizing a very general performance measure, which includes as a particular case the classical objectives in semi-obnoxious facility location. In general, the above-mentioned model yields a global optimization problem, whose resolution is dealt with using d...
-
作者：Freund, Robert M.; Vera, Jorge R.
作者单位：Massachusetts Institute of Technology (MIT); Pontificia Universidad Catolica de Chile
摘要：Consider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e. g., no domain ball containing or intersecting the set, etc.). The authors' interest in this problem stems from fundamental issues involving the interplay of (i) the computational complexity of computing a point in the set, (ii) the geometry of the set, and (iii) the stability or conditioning of the set under perturbation. Under suitable definitions...
-
作者：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...
