-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Grechuk, Bogdan; Molyboha, Anton; Zabarankin, Michael
作者单位：Stevens Institute of Technology
摘要：An approach to the Shannon and Renyi entropy maximization problems with constraints on the mean and law-invariant deviation measure for a random variable has been developed. The approach is based on the representation of law-invariant deviation measures through corresponding convex compact sets of nonnegative concave functions. A solution to the problem has been shown to have an alpha-concave distribution (log-concave for Shannon entropy), for which in the case of comonotone deviation measures...
-
作者：Buchbinder, Niv; Naor, Joseph (Seffi)
作者单位：Microsoft; Technion Israel Institute of Technology
摘要：We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorit...
-
作者：Salez, Justin; Shah, Devavrat
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Massachusetts Institute of Technology (MIT)
摘要：The random assignment problem asks for the minimum-cost perfect matching in the complete n x n bipartite graph K-nn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The zeta(2) limit in the random assignment problem. RSA 18 381-418], the optimal cost was shown to converge to zeta(2) as n -> infinity, as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys. 48 1451-1459] throu...
-
作者：Gurvich, Itay; Whitt, Ward
作者单位：Northwestern University; Columbia University
摘要：Motivated by call centers, we study large-scale service systems with multiple customer classes and multiple agent pools, each with many agents. We propose a family of routing rules called queue-and-idleness-ratio (QIR) rules. A newly available agent next serves the customer from the head of the queue of the class (from among those he is eligible to serve) whose queue length most exceeds a specified state-dependent proportion of the total queue length. An arriving customer is routed to the agen...
-
作者：Auslender, Alfred; Goberna, Miguel A.; Lopez, Marco A.
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet; Institut Polytechnique de Paris; Ecole Polytechnique; Universitat d'Alacant
摘要：In this paper we consider min-max convex semi-infinite programming. To solve these problems we introduce a unified framework concerning Remez-type algorithms and integral methods coupled with penalty and smoothing methods. This framework subsumes well-known classical algorithms, but also provides some new methods with interesting properties. Convergence of the primal and dual sequences are proved under minimal assumptions.
-
作者：Sanders, Peter; Sivadasan, Naveen; Skutella, Martin
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; Max Planck Society; Technical University of Berlin
摘要：Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several...
-
作者：Mertens, Jean-Francois; Neyman, Abraham; Rosenberg, Dinah
作者单位：Universite Catholique Louvain; Hebrew University of Jerusalem; Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); Universite Paris 13; heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We prove that games with absorbing states with compact action sets have a value.
