-
作者：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...
-
作者：Jianyong, L; Xiaobo, Z
作者单位：Chinese Academy of Sciences; Tsinghua University
摘要：In this paper we investigate average reward semi-Markov decision processes with a general multichain structure using a data-transformation method. By solving the transformed discrete-time average Markov decision processes, we can obtain significant and interesting information on the original average semi-Markov decision processes. If the original semi-Markov decision processes satisfy some appropriate conditions, then stationary optimal policies in the transformed discrete-time models are also...
-
作者：Jelenkovic, PR; Momcilovic, P
作者单位：Columbia University; International Business Machines (IBM); IBM USA
摘要：We provide a large deviation result for a random sum Sigma(n=0)(Nx) X-n, where N-x is a renewal counting process and {X-n}(ngreater than or equal to0) are i.i.d. random variables, independent of N-x, with a common distribution that belongs to a class of square root insensitive distributions. Asymptotically, the tails of these distributions are heavier than e(-rootx) and have zero relative decrease in intervals of length rootx, hence square root insensitive. Using this result we derive the asym...
