-
作者：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...
-
作者：Jelenkovic, P; Momcilovic, P
作者单位：Columbia University
摘要：We investigate the distribution of the waiting time V in a stable M/G/1 processor-sharing queue with traffic intensity p < 1. When the distribution of a customer service request B belongs to a large class of subexponential distributions with tails heavier than e(-rootx), it is shown that P[V > x] = P[B > (1 - p)x](1 + o(1)) as x --> infinity. Furthermore, we demonstrate that the preceding relationship does not hold if the service distribution has a lighter tail than e(-rootx).
-
作者：Cavazos-Cadena, R; Montes-de-Oca, R
作者单位：Universidad Autonoma Metropolitana - Mexico
摘要：This work concerns discrete-time Markov decision chains with finite state space and bounded costs. The controller has constant risk sensitivity A, and the performance of a control policy is measured by the corresponding risk-sensitive average cost criterion. Assuming that the optimality equation has a solution, it is shown that the value iteration scheme can be implemented to obtain, in a finite number of steps, (1) an approximation to the optimal A-sensitive average cost with an error less th...
-
作者：Cheung, D; Cucker, F; Peña, J
作者单位：Carnegie Mellon University
摘要：In recent years, several condition numbers were defined for a variety of linear programming problems based upon relative distances to ill-posedness. In this paper, we provide a unifying view of soma: of these condition numbers. To do so, we introduce yet another linear programming problem and show that its distance to ill-posedness naturally captures the most commonly used distances to ill-posedness.
-
作者：Nickel, S; Puerto, J; Rodriguez-Chia, AM
作者单位：Saarland University; University of Sevilla; Universidad de Cadiz
摘要：In this paper, we deal with single facility location problems in a general normed space in which the existing facilities are represented by convex sets of points. The criterion to be satisfied by the service facility is the minimization of an increasing, convex function of the distances from the service facility to the closest point of each demand set. We obtain a geometrical characterization of the set of optimal solutions for this problem. Two remarkable cases-the classical Weber problem and...
-
作者：Laurent, M
摘要：Sherali and Adams (1990), Lovasz and Schrijver, (1991) and, recently, Lasserre (2001b) have constructed hierarchies of successive linear or semidefinite relaxations of a 0-1 polytope P subset of or equal to R-n converging to P in n steps. Lasserre's approach uses results about representations of positive polynomials as sums of squares and the dual theory of moments. We present the three methods in a common elementary framework and show that the Lasserre construction provides the tightest relax...
-
作者：Orshan, G; Sudhölter, P
作者单位：Hebrew University of Jerusalem; Open University Israel; University of Southern Denmark
摘要：By means of an example, it is shown that the prenucleolus is not the only minimal solution that satisfies nonemptiness, Pareto optimality, covariance, the equal treatment property, and the reduced game property, even if the universe of players is infinite. This example also disproves a conjecture of Gurvich et al. (1994). As a second result, we prove that the prenucleolus is axiomatized by nonemptiness, covariance, the equal treatment property, and the reconfirmation property, provided the uni...
