-
作者：Jeanblanc, M; Lakner, P; Kadam, A
作者单位：Universite Paris Saclay; New York University; University of Michigan System; University of Michigan
摘要：In this paper we consider the optimization problem of an agent who wants to maximize the total expected discounted utility from consumption over an infinite horizon. The agent is under obligation to pay a debt at a fixed rate until he/she declares bankruptcy. At that point, after paying a fixed cost, the agent will be able to keep a certain fraction of the present wealth, and the debt will be forgiven. The selection of the bankruptcy time is taken to be at the discretion of the agent. The nove...
-
作者：Laraki, R; Sudderth, WD
作者单位：Centre National de la Recherche Scientifique (CNRS); heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique; University of Minnesota System; University of Minnesota Twin Cities
摘要：We give necessary and sufficient conditions for certain optimal reward operators to preserve continuity and Lipschitz continuity.
-
作者：Agrawal, R; Baccelli, F; Rajan, R
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：We introduce a network model that allows us to capture the time-varying service delivered to a traffic stream due to the presence of random perturbations (e.g., cross-traffic in a communication network). We first present the model for a single network element and then describe how such elements may be interconnected using the operations of fork and join. Such networks may be seen as a generalization of stochastic event graphs and of the class of fork-join networks. The departure processes in s...
-
作者：Anderson, EJ; Potts, CN
作者单位：University of New South Wales Sydney; University of Southampton
摘要：This paper considers the online scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a ...
-
作者：Chen, X; Simchi-Levi, D
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We analyze an infinite horizon, single-product, periodic review model in which pricing and production/inventory decisions are made simultaneously. Demands in different periods are identically distributed random variables that are independent of each other, and their distributions depend on the product price. Pricing and ordering decisions are made at the beginning of each period, and all shortages are backlogged. Ordering cost includes both a fixed cost and a variable cost proportional to the ...
-
作者：Johari, R; Tsitsiklis, JN
作者单位：Stanford University; Massachusetts Institute of Technology (MIT)
摘要：We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. We also consider extensions to a network context, where users submit individual payments for each link in the network they may wish to use. In this network model, we again show tha...
-
作者：Takine, T
作者单位：University of Osaka
摘要：This paper considers the steady-state solution of Markov chains of M/G/1 type. We first derive the matrix product form solution of the steady-state probability. This formula is considered as a natural generalization of the matrix-geometric solution of quasi birth-and-death processes to Markov chains of M/G/1 type. Based on this formula, we study the asymptotics of the tail distribution. For the light-tailed case, we show a sufficient condition for the geometric asymptotics of the tail distribu...
-
作者：de Farias, DP; Van Roy, B
作者单位：Massachusetts Institute of Technology (MIT); Stanford University
摘要：In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program-the ALP-that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m much less than M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by e...
-
作者：Karger, DR; Klein, P; Stein, C; Thorup, M; Young, NE
作者单位：Massachusetts Institute of Technology (MIT); Brown University; Columbia University; AT&T; University of California System; University of California Riverside
摘要：Given an undirected graph with edge costs and a subset of k greater than or equal to 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently, Calinescu et al. (Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for MULTIWAY CUT. J. Comput. System Sci. 60(3) 564-574) gave a novel geometr...
