-
作者：Schlicher, Loe; Slikker, Marco; van Jaarsveld, Willem; Van Houtum, Geert-Jan
作者单位：Eindhoven University of Technology
摘要：We study several service providers that keep spare parts in stock to protect for downtime of their high-tech machines and that face different downtime costs per stockout. Service providers can cooperate by forming a joint spare parts pool, and we study the allocation of the joint costs to the individual service providers by studying an associated cooperative game. In extant literature, the joint spare parts pool is typically controlled by a suboptimal full-pooling policy. A full-pooling policy...
-
作者：de Klerk, Etienne; Laurent, Monique
作者单位：Tilburg University; Delft University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Inter...
-
作者：Jansen, Klaus; Klein, Kim-Manuel
作者单位：University of Kiel
摘要：We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoss about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time vertical bar V vertical bar 2(O(d)) center dot enc(I)(O(1))...
-
作者：Burke, James, V; Engle, Abraham
作者单位：University of Washington; University of Washington Seattle
摘要：This work concerns the local convergence theory of Newton and quasi-Newton methods for convex composite optimization: where one minimizes an objective that can be written as the composition of a convex function with one that is continuiously differentiable. We focus on the case in which the convex function is a potentially infinite-valued piecewise linear-quadratic function. Such problems include nonlinear programming, minimax optimization, and estimation of nonlinear dynamics with non-Gaussia...
-
作者：Iwata, Satoru; Yokoi, Yu
作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The stable matching (or stable marriage) model of Gale and Shapley [Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9 15.] has been generalized in various directions, such as matroid kernels by Fleiner [Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards AMH, eds. Proc. 8th Internat. Conf. Integer Programming Combin. Optim., Lecture Notes in Computer Science, vol. 2081 (Springer-Verlag, Berlin), 105-...
-
作者：Sun, Ruoyu; Luo, Zhi-Quan; Ye, Yinyu
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Stanford University
摘要：Random permutation is observed to be powerful for optimization algorithms: for multiblock ADMM (alternating direction method of multipliers), whereas the classical cyclic version diverges, the randomly permuted version converges in practice; for BCD (block coordinate descent), the randomly permuted version is typically faster than other versions. In this paper we provide strong theoretical evidence that random permutation has positive effects on ADMM and BCD, by analyzing randomly permuted ADM...
-
作者：Keutchayan, Julien; Munger, David; Gendreau, Michel
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal
摘要：Stochastic programming problems generally lead to large-scale programs if the number of random outcomes is large or if the problem has many stages. A way to tackle them is provided by scenario-tree generation methods, which construct approximate problems from a reduced subset of outcomes. However, it is well known that the number of scenarios required to keep the approximation error within a given tolerance grows rapidly with the number of random parameters and stages. For this reason, to limi...
-
作者：Aghajani, Reza; Ramanan, Kavita
作者单位：University of California System; University of California San Diego; Brown University
摘要：We consider the so-called GI/GI/N queue, in which a stream of jobs with independent and identically distributed service times arrive as a renewal process to a common queue that is served by N identical parallel servers in a first-come, first-served manner. We introduce a new representation for the state of the system and, under suitable conditions on the service and interarrival distributions, establish convergence of the corresponding sequence of centered and scaled stationary distributions i...
-
作者：Wang, Mengdi
作者单位：Princeton University
摘要：We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted-reward and average-reward Markov decision problems. By leveraging the value-policy duality, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an f-optimal policy using nearly linear runtime in the worst case for a fixed value of the discount factor. When the Markov decision process is ergodic and speci...
-
作者：Solan, Eilon; Solan, Omri N.
作者单位：Tel Aviv University
摘要：We prove that every multiplayer quitting game admits a sunspot epsilon-equilibrium for every epsilon> 0, that is, an e-equilibrium in an extended game in which the players observe a public signal at every stage. We also prove that, if a certain matrix that is derived from the payoffs in the game is not a Q-matrix in the sense of linear complementarity problems, then the game admits a uniform epsilon-equilibrium for every epsilon > 0.
