3期

最新文章

• An Open Queueing Network with Asymptotically Stable Fluid Model and Unconventional Heavy Traffic Behavior AI翻译
  作者：Kruk, Lukasz
  作者单位：Maria Curie-Sklodowska University
  摘要：We provide an example of a feedforward first-in-system, first-out (FISFO) queueing network with unconventional, i.e., non-Brownian, heavy traffic diffusion approximation. We also prove that fluid models of subcritical feedforward earliest-deadline-first (EDF) queueing networks are asymptotically stable.
• Split Rank of Triangle and Quadrilateral Inequalities AI翻译
  作者：Dey, Santanu S.; Louveaux, Quentin
  作者单位：University System of Georgia; Georgia Institute of Technology; University of Liege
  摘要：A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and Cornuejols and Margot showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. From an example given by Cook et al. it is known that one particular class of facet-defining triangle inequality does...
• Tight Approximation Algorithms for Maximum Separable Assignment Problems AI翻译
  作者：Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim
  作者单位：Dartmouth College; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated; International Business Machines (IBM); IBM USA
  摘要：A separable assignment problem (S A P) is defined by a set of bins and a set of items to pack in each bin; a value, f(ij), for assigning item j to bin i; and a separate packing constraint for each bin-i.e., for each bin, a family of subsets of items that fit in to that bin. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (G A P)(1) and a distributed caching problem (DCP) described in this paper. Giv...
• Convergence of Stationary Points of Sample Average Two-Stage Stochastic Programs: A Generalized Equation Approach AI翻译
  作者：Ralph, Daniel; Xu, Huifu
  作者单位：University of Cambridge; University of Southampton
  摘要：This paper presents an asymptotic analysis of a Monte Carlo method, variously known as sample average approximation (SAA) or sample path optimization (SPO), for a general two-stage stochastic minimization problem. We study the case when the second-stage problem may have multiple local optima or stationary points that are not global solutions and SAA is implemented using a general nonlinear programming solver that is only guaranteed to find stationary points. New optimality conditions are devel...
• Flows and Decompositions of Games: Harmonic and Potential Games AI翻译
  作者：Candogan, Ozan; Menache, Ishai; Ozdaglar, Asuman; Parrilo, Pablo A.
  作者单位：Massachusetts Institute of Technology (MIT); Microsoft
  摘要：In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corre...
• Perfect Information Games with Upper Semicontinuous Payoffs AI翻译
  作者：Purves, Roger A.; Sudderth, William D.
  作者单位：University of California System; University of California Berkeley; University of Minnesota System; University of Minnesota Twin Cities
  摘要：It has been shown that every n-person, perfect information game with no chance moves and bounded, lower semicontinuous payoffs has a subgame perfect epsilon-equilibrium in pure strategies. Here the same is proved when the payoffs are bounded and upper semicontinuous.
• Generalized Differentiation with Positively Homogeneous Maps: Applications in Set-Valued Analysis and Metric Regularity AI翻译
  作者：Pang, C. H. Jeffrey
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We propose a new concept of generalized differentiation of set-valued maps that captures first-order information. This concept encompasses the standard notions of Frechet differentiability, strict differentiability, calmness and Lipschitz continuity in single-valued maps, and the Aubin property and Lipschitz continuity in set-valued maps. We present calculus rules, sharpen the relationship between the Aubin property and coderivatives, and study how metric regularity and open covering can be re...
• The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraints AI翻译
  作者：Ralph, Daniel; Stein, Oliver
  作者单位：University of Cambridge; Helmholtz Association; Karlsruhe Institute of Technology
  摘要：We introduce nondegeneracy and the C-index for C-stationary points of a QPCC, that is, for a mathematical program with a quadratic objective function and linear complementarity constraints. The C-index characterizes the qualitative local behavior of a QPCC around a nondegenerate C-stationary point. The article focuses on the structure of the C-stationary set of QPCCs depending on a real parameter. We show that, for generic QPCC data, the C-index changes exactly at turning points of the C-stati...
• Polynomial Matrix Inequality and Semidefinite Representation AI翻译
  作者：Nie, Jiawang
  作者单位：University of California System; University of California San Diego
  摘要：Consider a convex set S = {x is an element of D: G(x) >= 0}, where G(x) is a symmetric matrix whose every entry is a polynomial or rational function, D subset of R-n is a domain on which G(x) is defined, and G(x) >= 0 means G(x) is positive semidefinite. The set S is called semidefinite representable if it equals the projection of a higher dimensional set that is defined by a linear matrix inequality (LMI). This paper studies sufficient conditions guaranteeing semidefinite representability of ...