-
作者：Iyengar, GN
作者单位：Columbia University
摘要：In this paper we propose a robust formulation for discrete time dynamic programming (DP). The objective of the robust formulation is to systematically mitigate the sensitivity of the DP optimal policy to ambiguity in the underlying transition probabilities. The ambiguity is modeled by associating a set of conditional measures with each state-action pair. Consequently, in the robust formulation each policy has a set of measures associated with it. We prove that when this set of measures has a c...
-
作者：Balaji, R; Parthasarathy, T; Raman, DS; Vetrivel, V
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; University of Hyderabad; Indian Statistical Institute; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras
摘要：In this paper, we investigate the Lipschitz continuity of the solution map in semidefinite linear complementarity problems. For a monotone linear transformation defined on the space of real symmetric n x n matrices, we show that the Lipschitz continuity of the solution map implies the globally uniquely solvable (GUS)-property. For Lyapunov transformations with the Q-property, we prove that the Lipschitz continuity of the solution map is equivalent to the strong monotonicity property. For the d...
-
作者：Thibault, L; Zlateva, N
作者单位：Universite de Montpellier; University of Sofia; Universite de Montpellier
摘要：We study on a product Banach space the properties of a class of saddle functions called partially ball weakly inf-compact. For such a function we prove that the domain of the subdifferential is nonempty, that the operator naturally associated with the subdifferential is maximal monotone, and that the subdifferential of the function is integrable. For a function in a large subclass of that class we prove the density of the domain of the subdifferential in the domain of the function.
-
作者：Mannor, S; Tsitsiklis, JN
作者单位：McGill University; Massachusetts Institute of Technology (MIT)
摘要：We consider the empirical state-action frequencies and the empirical reward in weakly communicating finite-state Markov decision processes under general policies. We define a certain polytope and establish that every element of this polytope is the limit of the empirical frequency vector, under some policy, in a strong sense. Furthermore, we show that the probability of exceeding a given distance between the empirical frequency vector and the polytope decays exponentially with time under every...
-
作者：Dash, S
作者单位：International Business Machines (IBM); IBM USA
摘要：We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We establish an exponential lower bound on the length of branch-and-cut proofs that use 0-1 branching and lift-and-project cuts (called simple disjunctive cuts by some authors), Gomory-Chvatal cuts, and cuts arising from the No matrix-cut operator of Lovasz and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential runn...
-
作者：Ye, YY
作者单位：Stanford University
摘要：We present a new complexity result on solving the Markov decision problem (MDP) with n states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that when the discount factor theta is strictly less than 1, the problem can be solved in at most O(n(1.5)(log1/(1 - theta) + log n)) classical interior-point method iterations and O(n(4)(log 1/(1 - theta) + log n)) arithmetic operations. Our method is a combinatorial int...
-
作者：Marinacci, M; Montrucchio, L
作者单位：University of Turin; University of Turin
摘要：We study the properties of ultramodular functions, a class of functions that generalizes scalar convexity and that naturally arises in some economic and statistical applications.
-
作者：Zhang, JW; Chen, B; Ye, YY
作者单位：New York University; University of Warwick; Stanford University
摘要：We present a multiexchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2 root 2- epsilon and 3 + 2 root 2- + epsilon for any given constant epsilon > 0. The previously known best approximation ratio for the CFLP is 7.88, a...
-
作者：Shwartz, A; Weiss, A
作者单位：Technion Israel Institute of Technology; AT&T; Alcatel-Lucent; Lucent Technologies
摘要：The theory of large deviations for jump Markov processes has been generally proved only when jump rates are bounded below, away from zero (Dupuis and Ellis, 1995, The large deviations principle for a general class of queueing systems I. Trans. Amer Moth. Soc. 347 2689-2751; Ignatiouk-Robert, 2002, Sample path large deviations and convergence parameters. Ann. Appl. Probab. 11 1292-1329; Shwartz and Weiss, 1995, Large Deviations for Performance Analysis, Chapman-Hall). Yet, various applications ...
-
作者：Whitt, W
作者单位：Columbia University
摘要：We establish heavy-traffic stochastic-process limits for queue-length, waiting-time and overflow stochastic processes in a class of G/GI/n/m queueing models with n servers and m extra waiting spaces. We let the arrival process be general, only requiring that it satisfy a functional central limit theorem. To capture the impact of the service-time distribution beyond its mean within a Markovian framework, we consider a special class of service-time distributions, denoted by H-2(*), which are mix...
