-
作者：Gossner, O; Tomala, T
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Humanities & Social Sciences (INSHS); Universite PSL; Ecole Normale Superieure (ENS); Ecole des Hautes Etudes en Sciences Sociales (EHESS); Institut Polytechnique de Paris; Ecole des Ponts ParisTech; Northwestern University; Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS)
摘要：Let (x(n))(n) be a process with values in a finite set X and law P, and let y(n) = f(x(n)) be a function of the process. At stage n, the conditional distribution p(n) = P(x(n) vertical bar x(1),..., x(n-1)), element of Pi = Delta(X), is the belief that a perfect observer, who observes the process online, holds on its realization at stage n. A statistician observing the signals y1,..., y(n) holds a belief e(n) = P(p(n) vertical bar x(1),..., x(n)) is an element of Delta(Pi) on the possible pred...
-
作者：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...
-
作者：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 ...
-
作者：Mohebi, H; Rubinov, A
作者单位：Shahid Bahonar University of Kerman (SBUK); Federation University Australia
摘要：Necessary and sufficient conditions for a local minimum form a well-developed chapter of optimization theory. Determination of such conditions for the global minimum is a challenging problem. Useful conditions are currently known only for a few classes of nonconvex optimization problems. It is important to find different classes of problems for which the required conditions can be obtained. In this paper we examine one of these classes: the minimization of the distance to an arbitrary closed s...
-
作者：Arutyunov, A; Pereira, FL
作者单位：Peoples Friendship University of Russia; Universidade do Porto
摘要：In this article, we derive second-order necessary conditions of optimality for an abstract optimization problem with equality and inequality constraints and constraints in the form of an inclusion into a given closed set. An important feature is that our optimality conditions dispense with any a priori normality assumptions, such as Robinson's constraint qualification, and remain informative even for abnormal points. Moreover, our optimality conditions take into account the second-order effect...
-
作者：Bansal, N; Correa, JR; Kenyon, C; Sviridenko, M
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez; Brown University
摘要：We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm...
-
作者：Niño-Mora, J
作者单位：Universidad Carlos III de Madrid
摘要：This paper presents a framework grounded on convex optimization and economics ideas to solve by index policies problems of optimal dynamic allocation of effort to a discrete-state (finite or countable) binary-action (work/rest) semi-Markov restless bandit project, elucidating issues raised by previous work. Its contributions include: (i) the concept of a restless bandit's marginal productivity index (MPI), characterizing optimal policies relative to general cost and work measures; (ii) the cha...
-
作者：De Loera, JA; Hemmecke, R; Köppe, M; Weismantel, R
作者单位：University of California System; University of California Davis; Otto von Guericke University
摘要：We classify according to their computational complexity, integer optimization problems whose constraints and objective functions e polynomials with integer coefficients, and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are nonnegative over the polytope, these sequences of bounds lead to a fully polynomial-time approx...
