-
作者：Fekete, SP; Schepers, J
作者单位：Braunschweig University of Technology; International Business Machines (IBM); IBM Germany
摘要：Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instance in two- or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial str...
-
作者：Agrawal, R; Baccelli, F; Rajan, R
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：We introduce a network model that allows us to capture the time-varying service delivered to a traffic stream due to the presence of random perturbations (e.g., cross-traffic in a communication network). We first present the model for a single network element and then describe how such elements may be interconnected using the operations of fork and join. Such networks may be seen as a generalization of stochastic event graphs and of the class of fork-join networks. The departure processes in s...
-
作者：Anderson, EJ; Potts, CN
作者单位：University of New South Wales Sydney; University of Southampton
摘要：This paper considers the online scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a ...
-
作者：Dunn, RT; Glazebrook, KD
作者单位：University of Edinburgh
摘要：This paper is the first to consider general multiarmed bandit problems on parallel machines working at different speeds. Block allocation policies make a once-for-all allocation of bandits to machines at time zero. In this class we describe how to achieve Blackwell optimality under given conditions. The block allocation policy identified allocates the bandits with the largest guaranteed reward rates to the machines operating at greatest speed. This policy is shown to be average-reward optimal ...
-
作者：Powell, W; Ruszczynski, A; Topaloglu, H
作者单位：Princeton University; Rutgers University System; Rutgers University New Brunswick; Cornell University
摘要：We propose the use of sequences of separable, piecewise linear approximations for solving nondifferentiable stochastic optimization problems. The approximations are constructed adaptively using a combination of stochastic subgradient information and possibly sample information on the objective function itself. We prove the convergence of several versions of such methods when the objective function is separable and has integer break points, and we illustrate their behavior on numerical examples...
-
作者：Carr, R
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：The problem of separating a class of inequalities that are valid for the symmetric traveling salesman problem (STSP) consists of devising an efficient method that, given a fractional point x* for a relaxation of the STSP, either finds an inequality in the given class of STSP inequalities that is violated by x* or determines that there are no such violated inequalities. We can define important classes of STSP inequalities by performing Naddef's and Rinaldi's (1993) node-lifting operation on STS...
-
作者：Tseng, P
作者单位：University of Washington; University of Washington Seattle
摘要：The EM algorithm is a popular method for maximum likelihood estimation from incomplete. data. This method may be viewed as a proximal point method for maximizing the log-likelihood function using an integral form of the Kullback-Leibler distance function. Motivated by this interpretation, we consider a proximal point method using an integral form of entropy-like distance function. We give a convergence analysis of the resulting proximal point method in the case where the cluster points lie in ...
-
作者：Neyman, A; Smorodinsky, R
作者单位：Hebrew University of Jerusalem; Hebrew University of Jerusalem; Technion Israel Institute of Technology
摘要：The asymptotic value, introduced by Kannai in 1966, is an asymptotic approach to the notion of the Shapley value for games with infinitely many players. A vector measure game is a game v where the worth v(S) of a coalition S is a function f of mu(S) where mu is a vector measure. Special classes of vector measure games are the weighted majority games and the two-house weighted majority games, where a two-house weighted majority game is a game in which a coalition is winning if and only if it is...
-
作者：Kou, SC; Kou, SG
作者单位：Harvard University; Columbia University
摘要：Since growth stocks tend to have low or even negative earnings and high volatility, it is a great challenge to derive a meaningful mathematical model within the traditional valuation framework. This paper attempts to derive a suitable diffusion model for growth stocks by using the idea of size distribution. Numerical illustration of the model based on the data covering the time period of the recent boom and burst of the Internet bubble is also presented.
-
作者：Piunovskiy, AB
作者单位：University of Liverpool
摘要：In this paper an intervention refers to an immediate change of the state of the system; between interventions, the continuous-time jump Markov process is uncontrollable, with natural jump intensities. The multicriteria control problem for such a model is considered, and the constrained version is investigated with the help of the Lagrange multipliers technique. All of the theory is illustrated by an example of the optimal control of epidemic with carriers.
