-
作者：Andreani, Roberto; Martinez, Jose Mario; Ramos, Alberto; Silva, Paulo J. S.
作者单位：Universidade Estadual de Campinas; Universidade Federal do Parana
摘要：Sequential optimality conditions for constrained optimization are necessarily satisfied by local minimizers, independently of the fulfillment of constraint qualifications. These conditions support the employment of different stopping criteria for practical optimization algorithms. On the other hand, when an appropriate property on the constraints holds at a point that satisfies a sequential optimality condition, such a point also satisfies the Karush-Kuhn-Tucker conditions. Those properties wi...
-
作者：Bender, Christian; Gartner, Christian; Schweizerb, Nikolaus
作者单位：Saarland University; Tilburg University
摘要：We present a novel method for deriving tight Monte Carlo confidence intervals for solutions of stochastic dynamic programming equations. Taking some approximate solution to the equation as an input, we construct pathwise recursions with a known bias. Suitably coupling the recursions for lower and upper bounds ensures that the method is applicable even when the dynamic program does not satisfy a comparison principle. We apply our method to three nonlinear option pricing problems, pricing under ...
-
作者：Berczi, Kristof; Frank, Andras
作者单位：Eotvos Lorand University
摘要：The main result of this paper is motivated by the following two apparently unrelated graph optimization problems: (A) As an extension of Edmonds' disjoint branchings theorem, characterize digraphs comprising k disjoint branchings B-i each having a specified number mu(i) of arcs. (B) As an extension of Ryser's maximum term rank formula, determine the largest possible matching number of simple bipartite graphs complying with degree-constraints. The solutions to these problems and to their genera...
-
作者：Rujeerapaiboon, Napat; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：We derive sharp probability bounds on the tails of a product of symmetric nonnegative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, the probability bounds on the right tails can be evaluated analytically. The bounds under precise and imprecise covariance information coin...
-
作者：Berczi, Kristof; Frank, Andras
作者单位：Eotvos Lorand University
摘要：Ryser's max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with a specific matching number. In a previous paper by the authors, a generalization was developed for the case when the degrees are constrained by upper and lower bounds. Here, two other extensions of Ryser's theorem are discussed. The first one is a matroidal model, while the second one settles the augmentation version. In fact, the two directions...
-
作者：Eschenfeldt, Patrick; Gamarnik, David
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy-traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly two weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is comparable to that of...
-
作者：Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of California System; University of California Irvine
摘要：We introduce new classes of utility functions and production sets, called Leontief-free, which are applicable when goods are substitutes and utilities/ production are subadditive (to model inter-good satiation). When goods are complements, the well studied Leontief utility functions do an adequate job; however, to the best of our knowledge, a similar concept for the case of goods that are substitutes was not known. For markets with these utility functions and production sets, we obtain the fol...
-
作者：Ma, Will
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption is allowed, we provide a (1/2 - epsilon)-approximation, along with an example showing this is tight. When preemption isn't allowed, we provide a 1/12-approximati...
-
作者：Bansal, Nikhil; Kamphorst, Bart; Zwart, Bert
作者单位：Eindhoven University of Technology
摘要：For a GI/GI/1 queue, we show that the average sojourn time under the (blind) Randomized Multilevel Feedback algorithm is no worse than that under the Shortest Remaining Processing Time algorithm times a logarithmic function of the system load. Moreover, it is verified that this bound is tight in heavy traffic, up to a constant multiplicative factor. We obtain this result by combining techniques from two disparate areas: competitive analysis and applied probability.
-
作者：Murota, Kazuo
作者单位：Tokyo Metropolitan University
摘要：The multiple exchange property for matroid bases is generalized for valuated matroids and M-natural concave set functions. The proof is based on the Fenchel-type duality theorem in discrete convex analysis. The present result has an implication in economics: The strong no complementarities condition of Gul and Stacchetti is, in fact, equivalent to the gross substitutes condition of Kelso and Crawford.
