-
作者：Kojima, M; Takeda, A
作者单位：Institute of Science Tokyo; Tokyo Institute of Technology
摘要：This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by Kojima and Tuncel for approximating a convex relaxation of a compact subset F = {x is an element of C-o : p(x) :less than or equal to 0 (For Allp (.) is an element of P-F)} of the n-dimensional Euclidean space R-n. Here, C-o denotes a nonempty compact convex subset of R-n, and P-F, a set of finitely or infinitely many quadratic functions. We evaluate the number of iterations which the s...
-
作者：Bäuerle, N
作者单位：Ulm University
摘要：We consider optimal control problems for stochastic fluid models of the following type: Suppose (Z(t)) is a continuous-time Markov chain with finite state space. As long as Z(t) = z, the dynamics of the system at rime t are given by a function b(2)(u((.))), where u is a control we have to choose. A cost rate function c is given, depending on the state and the action. We want to control the system in such a way as to minimize the expected discounted cost over an infinite horizon. We will call a...
-
作者：Henderson, SG; Glynn, PW
作者单位：University of Michigan System; University of Michigan; Stanford University
摘要：We introduce a new class of density estimators, termed look-ahead density estimators, for performance measures associated with a Markov chain. Look-ahead density estimators are given for both transient and steady-state quantities. Look-ahead density estimators converge faster (especially in multidimensional problems) and empirically give visually superior results relative to more standard estimators, such as kernel density estimators. Several numerical examples that demonstrate the potential a...
-
作者：Ben-Tal, A; Nemirovski, A
作者单位：Technion Israel Institute of Technology
摘要：We demonstrate that a conic quadratic problem. (CQP) [GRAPHICS] is polynomially reducible to Linear Programming. We demonstrate this by constructing, for every epsilon is an element of (0, 1/2], an LP program (explicitly given in terms of epsilon and the data of (CQP)) (LP) [GRAPHICS] with the following properties: (i) the number dim x + dim u of variables and the number dim p of constraints in (LP) do not exceed [GRAPHICS] (ii) every Feasible solution x to (CQP) can be extended to a feasible ...
-
作者：Jansen, K; Porkolab, L
作者单位：University of Kiel; Imperial College London
摘要：We consider the problem of scheduling n independent jobs on m unrelated parallel machines where each job has to be processed by exactly one machine, processing job j on machine i requires p(ij) time units, and the objective is to minimize the makespan, i.e., the maximum job completion time. Focusing on the case when m is fixed, we present for both preemptive and nonpreemptive variants of the problem fully polynomial approximation schemes whose running times depend only linearly on n. We also s...
-
作者：Müller, A; Scarsini, M
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; G d'Annunzio University of Chieti-Pescara
摘要：We consider two random vectors X and Y, such that the components of X are dominated in the convex order by the corresponding components of Y. We want to find conditions under which this implies that any positive linear combination of the components of X is dominated in the convex order by the same positive linear combination of the components of Y. This problem has a motivation in the comparison of portfolios in terms of risk. The conditions for the above dominance will concern the dependence ...
-
作者：Balder, EJ
作者单位：Utrecht University
摘要：A number of fundamental results, centered around extensions of Prohorov's theorem, is proven for the ws-topology for measures on a product space. These results contribute to die foundations of stochastic decision theory. They also subsume the principal results of Young measure theory, which only considers product measures with a fixed, common marginal. Specializations yield the criterion for relative ws-compactness of Schal (1975), the refined characterizations of ws-convergence of Galdeano an...
-
作者：Whitt, W
作者单位：AT&T
摘要：We study the multidimensional reflection map on the spaces D([0, T], R-k) and D([0, infinity), R-k) of right-continuous R-k-valued functions on [0, T] or [0, infinity) with left limits, endowed with variants of the Skorohod (1956) M-l topology. The reflection map was used with the continuous mapping theorem by Harrison and Reiman (1981) and Reiman (1984) to establish heavy-traffic limit theorems with reflected Brownian motion limit processes for vector-valued queue length, waiting time, and wo...
-
作者：Burachik, RS; Svaiter, BF
作者单位：Universidade Federal do Rio de Janeiro; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：We propose a new kind of inexact scheme for a family of generalized proximal point methods for the monotone complementarity problem. These methods, studied by Auslender, Teboulle, and Ben-Tiba, converge under the sole assumption of existence of solutions. We prove convergence of our new scheme and discuss its implementability.
-
作者：Laruelle, A; Valenciano, F
作者单位：Universitat d'Alacant; University of Basque Country
摘要：We provide a new axiomatization of the Shapley-Shubik and the Banzhaf power indices in the domain of simple superadditive games by means of transparent axioms. Only anonymity is shared with the former characterizations in the literature. The rest of the axioms are substituted by more transparent ones in terms of power in collective decision-making procedures. In particular, a clear restatement and a weaker alternative for the transfer axiom are proposed. Only one axiom differentiates the chara...
