Mathematics of Operations Research

最新文章

• Stochastic Combinatorial Optimization with Controllable Risk Aversion Level AI翻译
  作者：So, Anthony Man-Cho; Zhang, Jiawei; Ye, Yinyu
  作者单位：Chinese University of Hong Kong; New York University; Stanford University
  摘要：Most of the recent work on 2-stage stochastic combinatorial optimization problems has focused on minimization of the expected cost or the worst-case cost of the solution. Those two objectives can be viewed as two extreme ways of handling risk. In this paper we propose to use a one-parameter family of functionals to interpolate between them. Although such a family has been used in the mathematical finance and stochastic programming literature before, its use in the context of approximation algo...
• Time Average Replicator and Best-Reply Dynamics AI翻译
  作者：Hofbauer, Josef; Sorin, Sylvain; Viossat, Yannick
  作者单位：University of Vienna; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique; Universite PSL; Universite Paris-Dauphine
  摘要：Using an explicit representation in terms of the logit map, we show, in a unilateral framework, that the time average of the replicator dynamics is a perturbed solution of the best-reply dynamics.
• Variational inequalities over perturbed polyhedral convex sets AI翻译
  作者：Lu, Shu; Robinson, Stephen M.
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of Wisconsin System; University of Wisconsin Madison
  摘要：This paper provides conditions for existence of a locally unique, Lipschitzian solution of a linear variational inequality posed over a polyhedral convex set in R-n under perturbation of either or both of the constant term in the variational inequality and the right-hand side of the system of linear constraints de. ning its feasible set. Conditions for perturbation of just the constant term are well known. Here we show that a suitable extension of those conditions suffices for the more general...
• Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure Occurs AI翻译
  作者：Asmussen, Soren; Fiorini, Pierre; Lipsky, Lester; Rolski, Tomasz; Sheahan, Robert
  作者单位：Aarhus University; University of Maine System; University of Southern Maine; University of Connecticut; University of Wroclaw
  摘要：Many processes must complete in the presence of failures. Different systems respond to task failure in different ways. The system may resume a failed task from the failure point (or a saved checkpoint shortly before the failure point), it may give up on the task and select a replacement task from the ready queue, or it may restart the task. The behavior of systems under the first two scenarios is well documented, but the third (RESTART) has resisted detailed analysis. In this paper we derive t...
• Approximate minimization of the regularized expected error over kernel models AI翻译
  作者：Kurkova, Vera; Sanguineti, Marcello
  作者单位：Czech Academy of Sciences; Institute of Computer Science of the Czech Academy of Sciences; University of Genoa
  摘要：Learning from data under constraints on model complexity is studied in terms of rates of approximate minimization of the regularized expected error functional. For kernel models with an increasing number n of kernel functions, upper bounds on such rates are derived. The bounds are of the form a/n+b/root n, where a and b depend on the regularization parameter and on properties of the kernel, and of the probability measure de. ning the expected error. As a special case, estimates of rates of app...
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems AI翻译
  作者：Benoit, Genevieve; Boyd, Sylvia
  作者单位：University of Ottawa
  摘要：The symmetric traveling salesman problem (STSP) is to find a minimum weight Hamiltonian cycle in a weighted complete graph on n nodes. One direction which seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the subtour elimination problem (SEP). A well-known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Finding the exact value for this integrality gap is challenging...
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games AI翻译
  作者：Dunkel, Juliane; Schulz, Andreas S.
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：Rosenthal's congestion games constitute one of the few known classes of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a single path from her origin to her destination at minimum cost, and the cost of using an arc depends only on the total number of players using that arc. A natural extension is to allow for players controlling different amounts of flow, which results in so-called weighted congestion games. ...
• Separation of nonconvex sets with general augmenting functions AI翻译
  作者：Nedic, Angelia; Ozdaglar, Asuman
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Massachusetts Institute of Technology (MIT)
  摘要：In this paper, we consider two geometric optimization problems that are dual to each other and characterize conditions under which the optimal values of the two problems are equal. This characterization relies on establishing separation results for nonconvex sets using general concave surfaces defined in terms of convex augmenting functions. We prove separation results for augmenting functions that are bounded from below, unbounded augmenting functions, and asymptotic augmenting functions.
• On near optimality of the set of finite-state controllers for average cost POMDP AI翻译
  作者：Yu, Huizhen; Bertsekas, Dimitri P.
  作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
  摘要：We consider the average cost problem for partially observable Markov decision processes (POMDP) with finite state, observation, and control spaces. We prove that there exists an E-optimal finite-state controller (FSC) functionally independent of initial distributions for any epsilon > 0, under the assumption that the optimal liminf average cost function of the POMDP is constant. As part of our proof, we establish that if the optimal liminf average cost function is constant, then the optimal li...
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity AI翻译
  作者：Dean, Brian C.; Goemans, Michel X.; Vondrak, Jan
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider a stochastic variant of the NP-hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution policy that maximizes the expected value of items successfully placed in the knapsack, where the final over. owing item contributes no value. We consider...