-
作者：Dupuis, Paul; Leder, Kevin; Wang, Hui
作者单位：Brown University; Columbia University
摘要：This paper considers buffer over flow probabilities for stable queueing systems with one server and different classes of arrivals. The service priority is given to the class of customers whose current weighted queue size is the largest (weighted-serve-the-longest-queue policy). We explicitly identify the exponential decay rate for the rare-event probabilities of interest and construct asymptotically optimal importance-sampling schemes for simulation.
-
作者：Chan, Carri W.; Farias, Vivek F.
作者单位：Stanford University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This paper presents a general class of dynamic stochastic optimization problems we refer to as stochastic depletion problems. A number of challenging dynamic optimization problems of practical interest are stochastic depletion problems. Optimal solutions for such problems are difficult to obtain, both from a pragmatic computational perspective as well as from a theoretical perspective. As such, simple heuristics are desirable. We isolate two simple properties that, if satisfied by a problem wi...
-
作者：Klein, Manuel
作者单位：INSEAD Business School
摘要：In a recent contribution to this journal, Decamps et al. [Decamps, J.-P., T. Mariotti, S. Villeneuve. 2005. Investment timing under incomplete information. Math. Oper. Res. 30(2) 472-500] analyze the decision of when to invest in a project whose value is perfectly observable but driven by a parameter that is unknown to the decision maker ex ante. Using filtering and martingale techniques, they find that (i) the decision maker always benefits from an uncertain drift relative to an average drift...
-
作者：Akan, Mustafa; Ata, Baris
作者单位：Carnegie Mellon University; Northwestern University
摘要：We consider a continuous-time, rate-based model of network revenue management. Under mild assumptions, we construct a simple epsilon- optimal bid-price control, which can be viewed as a perturbation of a bid-price control in the classical sense [Williamson, E. L. 1992. Airline network seat control. Ph.D. thesis, MIT, Cambridge, MA]. We show that the associated bid-price process forms a martingale and the corresponding booking controls converge in an appropriate sense to an optimal control as e...
-
作者：Nagarajan, Viswanath; Sviridenko, Maxim
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA
摘要：In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,..., m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs sigma: [n] -> [n] that minimizes the maximum job completion time (makespan) of the schedule resulting f...
-
作者：Litvak, Nelly; Ejov, Vladimir
作者单位：University of Twente; University of South Australia
摘要：We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental...
-
作者：Yu, Jia Yuan; Mannor, Shie; Shimkin, Nahum
作者单位：McGill University; Technion Israel Institute of Technology
摘要：We consider a learning problem where the decision maker interacts with a standard Markov decision process, with the exception that the reward functions vary arbitrarily over time. We show that, against every possible realization of the reward process, the agent can perform as well-in hindsight-as every stationary policy. This generalizes the classical no-regret result for repeated games. Specifically, we present an efficient online algorithm-in the spirit of reinforcement learning-that ensures...
-
作者：Guo, Xin; Jarrow, Robert A.; Zeng, Yan
作者单位：University of California System; University of California Berkeley; Cornell University
摘要：Incomplete information is at the heart of information-based credit risk models. In this paper, we rigorously define incomplete information with the notion of delayed filtrations. We characterize two distinct types of delayed information, continuous and discrete: the first generated by a time change of filtrations and the second by finitely many marked point processes. This notion unifies the noisy information in Duffie and Lando [Duffie, D., D. Lando. 2001. Term structures and credit spreads w...
-
作者：Nagarajan, Viswanath; Sviridenko, Maxim
作者单位：International Business Machines (IBM); IBM USA
摘要：Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n x n symmetric nonnegative matrices W = (w(i,j)) and D = (d(i,j)). Given matrices W, D, and a permutation pi: [n] -> [n], the objective function is Q(pi) := Sigma(i,j is an element of[n], i not equal j) w(i,j) . d(pi(i), pi(j)...
-
作者：Faenza, Yuri; Kaibel, Volker
作者单位：University of Rome Tor Vergata; Otto von Guericke University
摘要：We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch [Kaibel, V., M. E. Pfetsch. 2008. Packing and partitioning orbitopes. Math. Programming, Ser. A 114(1) 1-36]. These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, respectively, exactly one 1-entry per row. They are important objects for symmetry reduction in certain integer...
