-
作者：De Loera, Jesus A.; Klee, Steven
作者单位：University of California System; University of California Davis
摘要：Provan and Billera defined the notion of weak k-decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly k-decomposable simplicial complex Delta is bounded above by a polynomial function of the number of k-faces in Delta and its dimension. For weakly 0-decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non-weakly 0-decomposab...
-
作者：Basu, Amitabh; Cornuejols, Gerard; Margot, Francois
作者单位：University of California System; University of California Davis; Carnegie Mellon University; Aix-Marseille Universite
摘要：We consider mixed-integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a rational lattice-free polytope L is finite if and only if the integer points on the boundary of L satisfy a certain 2-hyperplane ...
-
作者：Mandelbaum, Avishai; Momcilovic, Petar
作者单位：Technion Israel Institute of Technology; State University System of Florida; University of Florida
摘要：The asymptotic many-server queue with abandonments, G/GI/N + GI, is considered in the quality- and efficiency-driven (QED) regime. Here the number of servers and the offered load are related via the square-root rule, as the number of servers increases indefinitely. QED performance entails short waiting times and scarce abandonments (high quality) jointly with high servers' utilization (high efficiency), which is feasible when many servers cater to a single queue. For the G/GI/N + GI queue, we ...
-
作者：Ciocan, Dragos Florin; Farias, Vivek
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The present paper develops a simple, easy to interpret algorithm for a large class of dynamic allocation problems with unknown, volatile demand. Potential applications include ad display problems and network revenue management problems. The algorithm operates in an online fashion and relies on reoptimization and forecast updates. The algorithm is robust (as witnessed by uniform worst-case guarantees for arbitrarily volatile demand) and in the event that demand volatility (or equivalently devia...
-
作者：Jasin, Stefanus; Kumar, Sunil
作者单位：University of Michigan System; University of Michigan; University of Chicago
摘要：We consider a network revenue management problem with customer choice and exogenous prices. We study the performance of a class of certainty-equivalent heuristic control policies. These heuristics periodically re-solve the deterministic linear program (DLP) that results when all future random variables are replaced by their average values and implement the solutions in a probabilistic manner. We provide an upper bound for the expected revenue loss under such policies when compared to the optim...
-
作者：Xu, Huan; Mannor, Shie
作者单位：National University of Singapore; Technion Israel Institute of Technology
摘要：We consider Markov decision processes where the values of the parameters are uncertain. This uncertainty is described by a sequence of nested sets (that is, each set contains the previous one), each of which corresponds to a probabilistic guarantee for a different confidence level. Consequently, a set of admissible probability distributions of the unknown parameters is specified. This formulation models the case where the decision maker is aware of and wants to exploit some (yet imprecise) a p...
-
作者：Manshadi, Vahideh H.; Gharan, Shayan Oveis; Saberi, Amin
作者单位：Massachusetts Institute of Technology (MIT); Stanford University
摘要：We consider the online stochastic matching problem proposed by Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 - 1/e. Annual IEEE Sympos. Foundations Comput. Sci. 117-126] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribut...
-
作者：Henrion, Rene; Moeller, Andris
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：We provide an explicit gradient formula for linear chance constraints under a (possibly singular) multivariate Gaussian distribution. This formula allows one to reduce the calculus of gradients to the calculus of values of the same type of chance constraints (in smaller dimension and with different distribution parameters). This is an important aspect for the numerical solution of stochastic optimization problems because existing efficient codes for, e.g., calculating singular Gaussian distrib...
-
作者：Fibich, Gadi; Gavish, Nir
作者单位：Tel Aviv University
摘要：We introduce a new approach for analysis and numerical simulations of asymmetric first-price auctions, which is based on dynamical systems. We apply this approach to asymmetric auctions in which players' valuations are power-law distributed. We utilize a dynamical-systems formulation to provide a proof of the existence and uniqueness of the equilibrium strategies in the cases of two coalitions and of two types of players. In the case of n different players, the singular point of the original s...
-
作者：Del Pia, Alberto
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Let L be a family of lattice-free polyhedra in R-m containing the splits. Given a polyhedron P in Rm+n, we characterize when a valid inequality for P boolean AND (Z(n) x R-n) can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L. We also characterize the lattice-free polyhedra M such that all the disjunctive cuts corresponding to M can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L for every polyhedron P. Our resu...
