Mathematics of Operations Research

最新文章

• Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging AI翻译
  作者：Atar, Rami; Lev-Ari, Anat
  作者单位：Technion Israel Institute of Technology
  摘要：Scheduling control for a single-server queue with I customer classes and reneging is considered, with linear holding or reneging cost. An asymptotically optimal (AO) policy in heavy traffic is identified where classes are prioritized according to a workload-dependent dynamic index rule. Denote by c(i), mu(i), and theta(i), i is an element of J := {1, . . . , I} the queue length cost, service rate, and reneging rate, for class-i customers. Then, a relabeling of the classes and a partition 0 = w...
• The Complexity of Simple Models-A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem AI翻译
  作者：Bomze, Immanuel M.; Schachinger, Werner; Ullrich, Reinhard
  作者单位：University of Vienna
  摘要：In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which is closely related to practical difficulties in solving StQPs globally. In this study, we improve on existing lower bounds for the number of strict local solutions by ...
• Risk-Sensitive Asset Management and Cascading Defaults AI翻译
  作者：Birge, John R.; Bo, Lijun; Capponi, Agostino
  作者单位：University of Chicago; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Chinese Academy of Sciences; Columbia University
  摘要：We consider an optimal risk-sensitive portfolio allocation problem accounting for the possibility of cascading defaults. Default events have an impact on the distress state of the surviving stocks in the portfolio. We study the recursive system of non-Lipschitz quasilinear parabolic HJB-PDEs associated with the value function of the control problem in the different default states of the economy. We show the existence of a classical solution to this system via super-sub solution techniques and ...
• Robust Randomized Matchings AI翻译
  作者：Matuschke, Jannik; Skutella, Martin; Soto, Jose A.
  作者单位：Technical University of Munich; Technical University of Munich; Technical University of Berlin; Universidad de Chile; Universidad de Chile
  摘要：The following game is played on a weighted graph: Alice selects a matching M and Bob selects a number k. Alice's payoff is the ratio of the weight of the k heaviest edges of M to the maximum weight of a matching of size at most k. If M guarantees a payoff of at least a then it is called alpha-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a 1/root 2 -robust matching, which is best possible. We show that Alice can improve her payoff to 1/ln(4) by playing a randomized stra...
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs AI翻译
  作者：Dey, Santanu S.; Molinaro, Marco; Wang, Qianyi
  作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
  摘要：In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the lin...
• Strategic Influence in Social Networks AI翻译
  作者：Grabisch, Michel; Mandel, Antoine; Rusinowska, Agnieszka; Tanimura, Emily
  作者单位：Paris School of Economics; Paris School of Economics; Centre National de la Recherche Scientifique (CNRS)
  摘要：We consider a model of influence with a set of nonstrategic agents and two strategic agents. The nonstrategic agents have initial opinions and are linked through a simply connected network. They update their opinions as in the DeGroot model. The two strategic agents have fixed and opposed opinions. They each form a link with a nonstrategic agent in order to influence the average opinion that emerges due to interactions in the network. This procedure defines a zero-sum game whose players are th...
• Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures AI翻译
  作者：Jiang, Daniel R.; Powell, Warren B.
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Princeton University
  摘要：In this paper, we consider a finite-horizon Markov decision process (MDP) for which the objective at each stage is to minimize a quantile-based risk measure (QBRM) of the sequence of future costs; we call the overall objective a dynamic quantile-based risk measure (DQBRM). In particular, we consider optimizing dynamic risk measures where the one-step risk measures are QBRMs, a class of risk measures that includes the popular value at risk (VaR) and the conditional value at risk (CVaR). Althoug...
• When Is the Matching Polytope Box-Totally Dual Integral? AI翻译
  作者：Ding, Guoli; Tan, Lei; Zang, Wenan
  作者单位：Louisiana State University System; Louisiana State University; University of Hong Kong
  摘要：Let G = (V, E) be a graph. The matching polytope of G, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds [10] [Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69(1-2):125-130.], P(G) is determined by the following linear system pi(G): x(e) (3) 0 for each e is an element of E; x(delta(v)) <= 1 for each v is an element of V; and x(E[U]) <= left perpendicular(1/2)|U|right perpendicula...
• A Single-Phase, Proximal Path-Following Framework AI翻译
  作者：Quoc Tran-Dinh; Kyrillidis, Anastasios; Cevher, Volkan
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; Rice University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：We propose a new proximal path-following framework for a class of constrained convex problems. We consider settings where the nonlinear-and possibly nonsmooth-objective part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our approach relies on the following two main ideas. First, we reparameterize the optimality condition as an auxiliary problem, such that a good initial point is available; by doing so, a family of alternative paths tow...
• Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms AI翻译
  作者：Lu, Zhaosong; Li, Xiaorui
  作者单位：Simon Fraser University
  摘要：In the context of sparse recovery, it is known that most of the existing regularizers such as l(1) suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We show that every local minimizer of these models is substantially sparse or the magnitude of all of its nonzero entries is above a uniform constant depending only on th...