Mathematics of Operations Research

最新文章

• Equilibria and Systemic Risk in Saturated Networks AI翻译
  作者：Massai, Leonardo; Como, Giacomo; Fagnani, Fabio
  作者单位：Polytechnic University of Turin; Lund University
  摘要：We undertake a fundamental study of network equilibria modeled as solutions of fixed-point equations for monotone linear functions with saturation nonlinearities. The considered model extends one originally proposed to study systemic risk in networks of financial institutions interconnected by mutual obligations. It is one of the simplest continuous models accounting for shock propagation phenomena and cascading failure effects. This model also characterizes Nash equilibria of constrained quad...
• Data Exploration by Representative Region Selection: Axioms and Convergence AI翻译
  作者：Estes, Alexander S.; Ball, Michael O.; Lovell, David J.
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
  摘要：We present a new type of unsupervised learning problem in which we find a small set of representative regions that approximates a larger data set. These regions may be presented to a practitioner along with additional information in order to help the practitioner explore the data set. An advantage of this approach is that it does not rely on cluster structure of the data. We formally define this problem, and we present axioms that should be satisfied by functions that measure the quality of re...
• Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time AI翻译
  作者：Huang, Yu-Jui; Zhou, Zhou
  作者单位：University of Colorado System; University of Colorado Boulder; University of Sydney
  摘要：A new definition of continuous-time equilibrium controls is introduced. As opposed to the standard definition, which involves a derivative-type operation, the new definition parallels how a discrete-time equilibrium is defined and allows for unambiguous economic interpretation. The terms strong equilibria and weak equilibria are coined for controls under the new and standard definitions, respectively. When the state process is a time-homogeneous continuous-time Markov chain, a careful asymptot...
• Fair Cake Division Under Monotone Likelihood Ratios AI翻译
  作者：Barman, Siddharth; Rathi, Nidhi
  作者单位：Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
  摘要：This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. Although multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likeliho...
• Distributed Stochastic Optimization with Large Delays AI翻译
  作者：Zhou, Zhengyuan; Mertikopoulos, Panayotis; Bambos, Nicholas; Glynn, Peter; Ye, Yinyu
  作者单位：New York University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Stanford University
  摘要：The recent surge of breakthroughs in machine learning and artificial intelligence has sparked renewed interest in large-scale stochastic optimization problems that are universally considered hard. One of the most widely used methods for solving such problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochastic gradient descent on distributed computing architectures (possibly) asychronously. However, a key obstacle in ...
• Sufficient Optimality Conditions in Bilevel Programming AI翻译
  作者：Mehlitz, Patrick; Zemkoho, Alain B.
  作者单位：Brandenburg University of Technology Cottbus; University of Southampton
  摘要：This paper is concerned with the derivation of first- and second-order sufficient optimality conditions for optimistic bilevel optimization problems involving smooth functions. First-order sufficient optimality conditions are obtained by estimating the tangent cone to the feasible set of the bilevel program in terms of initial problem data. This is done by exploiting several different reformulations of the hierarchical model as a singlelevel problem. To obtain second-order sufficient optimalit...
• Analyzing Approximate Value Iteration Algorithms AI翻译
  作者：Ramaswamy, Arunselvan; Bhatnagar, Shalabh
  作者单位：University of Paderborn; Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
  摘要：In this paper, we consider the stochastic iterative counterpart of the value iteration scheme wherein only noisy and possibly biased approximations of the Bellman operator are available. We call this counterpart the approximate value iteration (AVI) scheme. Neural networks are often used as function approximators, in order to counter Bellman's curse of dimensionality. In this paper, they are used to approximate the Bellman operator. Because neural networks are typically trained using sample da...
• Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems AI翻译
  作者：Gamarnik, David; Tsitsiklis, John N.; Zubeldia, Martin
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
  摘要：We consider a heterogeneous distributed service system consisting of n servers with unknown and possibly different processing rates. Jobs with unit mean arrive as a renewal process of rate proportional to n and are immediately dispatched to one of several queues associated with the servers. We assume that the dispatching decisions are made by a central dispatcher with the ability to exchange messages with the servers and endowed with a finite memory used to store information from one decision ...
• Stability and Instability of the MaxWeight Policy AI翻译
  作者：Bramson, Maury; D'Auria, Bernardo; Walton, Neil
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; Universidad Carlos III de Madrid; University of Manchester
  摘要：Consider a switched queueing network with general routing among its queues. TShe MaxWeight policy assigns available service by maximizing the objective function Sigma(j)Q(j)sigma(j) among the different feasible service options, where Q(j) denotes queue size and sigma(j) denotes the amount of service to be executed at queue j. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. These properties and its simple formulation suggest M...
• Strong Algorithms for the Ordinal Matroid Secretary Problem AI翻译
  作者：Soto, Jose A.; Turkieltaub, Abner; Verdugo, Victor
  作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; University of British Columbia; Universidad de O'Higgins
  摘要：In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if every element from the optimum appears with probability 1/alpha in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitiv...