-
作者：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...
-
作者：Bockmayr, A; Eisenbrand, F
作者单位：Universite de Lorraine; Max Planck Society
摘要：The elementary closure P' of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P' is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P' are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elemen...
-
作者：Peña, J
作者单位：Carnegie Mellon University
摘要：Given a convex program and its dual, we analyze the conditioning of the primal-dual system of constraints, obtained by putting the primal and dual constraints together. We show that the conditioning of the primal-dual system can be estimated in terms of the conditioning of the primal and dual systems. In particular, provided both the primal and dual systems are well-conditioned. the primal-dual system is well-conditioned. We also investigate how the conditioning of the primal-dual system relat...
