-
作者：Calvin, James M.; Nakayama, Marvin K.
作者单位：New Jersey Institute of Technology
摘要：We describe an extension procedure for constructing new standardized time series procedures from existing ones. The approach is based on averaging over sample paths obtained by permuting path segments. Analytical and empirical results indicate that permuting improves standardized time series methods. We compare permuting to an alternative extension procedure known as batching. We demonstrate the permuting method by applying it to estimators based on the maximum and the area of a normalized path.
-
作者：Becchetti, L; Leonardi, S; Marchetti-Spaccamela, A; Schäfer, G; Vredeveld, T
作者单位：Sapienza University Rome; Technical University of Berlin; Maastricht University
摘要：In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng [25] to explain the behavior of algorithms that work well in practice while performing very poorly from a worst-case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of co...
-
作者：Gowda, MS; Sznajder, R
作者单位：University System of Maryland; University of Maryland Baltimore County; University System of Maryland; Bowie State University
摘要：Generalizing the P-property of a matrix, Gowda et al. [Gowda, M. S., R. Sznajder, J. Tao. 2004. Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 393 203-232] recently introduced and studied P- and globally uniquely solvable (GUS)-properties for linear transformations defined on Euclidean Jordan algebras. In this paper, we study the invariance of these properties under automorphisms of the algebra and of the symmetric cone. By means of these automo...
-
作者：de Farias, Daniela Pucci; Van Roy, Benjamin
作者单位：Massachusetts Institute of Technology (MIT); Stanford University; Stanford University
摘要：We introduce a new algorithm based on linear programming for optimization of average-cost Markov decision processes (MDPs). The algorithm approximates the differential cost function of a perturbed MDP via a linear combination of basis functions. We establish a bound on the performance of the resulting policy that scales gracefully with the number of states without imposing the strong Lyapunov condition required by its counterpart in de Farias and Van Roy (de Farias, D. R, B. Van Roy. 2003. The...
-
作者：Gaudioso, M; Giallombardo, G; Miglionico, G
作者单位：University of Calabria
摘要：We introduce a new approach to minimizing a function defined as the pointwise maximum over finitely many convex real functions (next referred to as the component functions), with the aim of working on the basis of incomplete knowledge of the objective function. A descent algorithm is proposed, which need not require at the current point the evaluation of the actual value of the objective function, namely, of all the component functions, thus extending to min-max problems the philosophy of the ...
-
作者：Garg, Rahul; Kapoor, Sanjiv
作者单位：International Business Machines (IBM); IBM India
摘要：In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of goods. The market equilibrium problem is to compute a price vector that ensures market clearing, i.e., the demand of a positively priced good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in economics. This paper presents a formulation of the ma...
-
作者：Arutyunov, Aram K.; Izmailov, Alexey F.
作者单位：Peoples Friendship University of Russia; Lomonosov Moscow State University
摘要：We develop a new regularity concept, unifying metric regularity, Robinson's constraint qualification, and directional regularity. We present the directional stability theorem and the related concept of directional metric regularity. On one hand, our directional stability theorem immediately implies Robinson's stability theorem [Arutyunov, A. V 2005. Covering of nonlinear maps on cone in neighborhood of abnormal point. Math. Notes 77 447-460.] as a particular case, while on the other hand, our ...
-
作者：Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Cornell University; Cornell University
摘要：We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multistage assembly problem. These inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. For each of these problems, we wish to balance the cost of maintaining surplus inventory for future demand against the cost of replenishing inventory more frequently. Fo...
-
作者：Cesa-Bianchi, Nicolo; Lugosi, Gabor; Stoltz, Gilles
作者单位：University of Milan; Pompeu Fabra University; ICREA; Pompeu Fabra University; Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
摘要：We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We study Hannan-consistent players for these games, that is, randomized playing strategies whose per-round regret vanishes with probability one as the number n of game rounds goes to infinity. We prove a general lower bound of Omega(n(-1/3)) for the convergence rate of the regret, and exhibit a specif...
-
作者：Kalai, Adam Tauman; Vempala, Santosh
作者单位：Toyota Technological Institute - Chicago; Massachusetts Institute of Technology (MIT)
摘要：We apply the method known as simulated annealing to the following problem in convex optimization: Minimize a linear function over an arbitrary convex set, where the convex set is specified only by a membership oracle. Using distributions from the Boltzmann-Gibbs family leads to an algorithm that needs only O*(root n) phases for instances in R-n. This gives an optimization algorithm that makes O*(n(4.5)) calls to the membership oracle, in the worst case, compared to the previous best guarantee ...
