-
作者：Davis, Chad; Hare, Warren
-
作者：Benaim, Michel; Faure, Mathieu
作者单位：University of Neuchatel; Centre National de la Recherche Scientifique (CNRS); Aix-Marseille Universite
摘要：We discuss consistency of vanishingly smooth fictitious play, a strategy in the context of game theory, which can be regarded as a smooth fictitious play procedure, where the smoothing parameter is time dependent and asymptotically vanishes. This answers a question initially raised by Drew Fudenberg and Satoru Takahashi.
-
作者：Kulik, Ariel; Shachnai, Hadas; Tamir, Tami
作者单位：Technion Israel Institute of Technology; Reichman University
摘要：Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the ...
-
作者：d'Aspremont, Alexandre; El Karoui, Noureddine
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; University of California System; University of California Berkeley
摘要：We study a weaker formulation of the nullspace property which guarantees recovery of sparse signals from linear measurements by l(1) minimization We require this condition to hold only with high probability, given a distribution on the nullspace of the coding matrix A. Under some assumptions on the distribution of the reconstruction error, we show that testing these weak conditions means bounding the optimal value of two classical graph partitioning problems: the k-Dense-Subgraph and MaxCut pr...
-
作者：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...
