-
作者：Kunnumkal, Sumit; Talluri, Kalyan
作者单位：Indian School of Business (ISB); Imperial College London
摘要：The network revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale products use multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationally intractable because of an exponentially large state space, and a number of heuristics have been proposed to approximate its value function. In this paper we show that the piecewise-linear approximation to the network RM dynamic program is tractable; speci...
-
作者：Mucha, Marcin; Sviridenko, Maxim
作者单位：University of Warsaw; Yahoo! Inc; University of Warwick
摘要：In this paper, we study the classical no-wait flowshop scheduling problem with makespan objective (F vertical bar no-wait vertical bar C-max in the standard three-field notation). This problem is well known to be a special case of the asymmetric traveling salesman problem (ATSP) and as such has an approximation algorithm with logarithmic performance guarantee. In this work, we show a reverse connection, we show that any polynomial time alpha-approximation algorithm for the no-wait flowshop sch...
-
作者：Cardaliaguet, Pierre; Rainer, Catherine; Rosenberg, Dinah; Vieille, Nicolas
作者单位：Universite PSL; Universite Paris-Dauphine; Universite de Bretagne Occidentale; Hautes Etudes Commerciales (HEC) Paris
摘要：We study the asymptotics of a class of two-player, zero-sum stochastic game with incomplete information on one side when the time span between two consecutive stages vanishes. The informed player observes the realization of a Markov chain on which the payoffs depend, whereas the noninformed player only observes his opponent's actions. We show the existence of a limit value; this value is characterized through an auxiliary optimization problem and as the solution of a Hamilton-Jacobi equation.
-
作者：Balkenborg, Dieter; Vermeulen, Dries
作者单位：University of Exeter; Maastricht University
摘要：A minimal diversity game is an n player strategic form game in which each player has m pure strategies at his disposal. The payoff to each player is always 1, unless all players select the same pure strategy, in which case, all players receive zero payoff. Such a game has a unique isolated completely mixed Nash equilibrium in which each player plays each strategy with equal probability, and a connected component of Nash equilibria consisting of those strategy profiles in which each player rece...
-
作者：Gortz, Inge Li; Molinaro, Marco; Nagarajan, Viswanath; Ravi, R.
作者单位：Technical University of Denmark; University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan; Carnegie Mellon University
摘要：The capacitated vehicle routing problem (CVRP) involves distributing identical items from a depot to a set of demand locations using a single capacitated vehicle. We introduce the heterogeneous capacitated vehicle routing problem, a generalization of CVRP to the setting of multiple vehicles having nonuniform speeds, and present for it a constant-factor approximation algorithm. Our main contribution is an approximation algorithm for the heterogeneous traveling salesman problem, which is the spe...
-
作者：Epstein, Leah; Levin, Asaf; van Stee, Rob
作者单位：University of Haifa; Technion Israel Institute of Technology; University of Leicester
摘要：We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrea...
-
作者：Bouchard, Bruno; Nutz, Marcel
作者单位：Universite PSL; Universite Paris-Dauphine; Institut Polytechnique de Paris; ENSAE Paris; Columbia University; Columbia University
摘要：We study a class of stochastic target games where one player tries to find a strategy such that the state process almost surely reaches a given target, no matter which action is chosen by the opponent. Our main result is a geometric dynamic programming principle, which allows us to characterize the value function as the viscosity solution of a nonlinear partial differential equation. Because abstract measurable selection arguments cannot be used in this context, the main obstacle is the constr...
-
作者：Beck, Amir; Hallak, Nadav
作者单位：Technion Israel Institute of Technology
摘要：We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve because the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to be nonconvex. We begin with a study of the properties of the orthogonal projection operator onto sparse symmetric sets. Based on this study, we derive efficient methods for computing sparse projectio...
-
作者：Braverman, Mark; Chen, Jing; Kannan, Sampath
作者单位：Princeton University; State University of New York (SUNY) System; Stony Brook University; University of Pennsylvania; Institute for Advanced Study - USA; Princeton University
摘要：We investigate computational and mechanism design aspects of allocating medical treatments at hospitals of different costs to patients who each value these hospitals differently. The payer wants to ensure that the total cost of all treatments is at most the budget, B. Access to overdemanded hospitals is rationed through waiting times. We first show that optimizing social welfare in equilibrium is NP-hard. But if the number of hospitals is small and the budget can be relaxed to (1 + epsilon)B f...
-
作者：Cavazos-Cadena, Rolando; Hernandez-Hernandez, Daniel
作者单位：CIMAT - Centro de Investigacion en Matematicas
摘要：This work is concerned with finite-state irreducible Markov decision chains satisfying continuity-compactness requirements. It is supposed that the system is driven by a decision maker with utility function U, which, aside mild conditions, is arbitrary, and the performance of a control policy is measured by the long-run average cost criterion induced by U. The main conclusions about this performance index are as follows: (i) the optimal U-average value function coincides with the optimal V-ave...
