-
作者：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...
-
作者：Olszewski, Wojciech; Sandroni, Alvaro
作者单位：Northwestern University; University of Pennsylvania; Northwestern University
摘要：Theories can be produced by experts seeking a reputation for having knowledge. Hence, a tester could anticipate that theories may have been strategically produced by uninformed experts who want to pass an empirical test. We show that, with no restriction on the domain of permissible theories, strategic experts cannot be discredited for an arbitrary but given number of periods, no matter which test is used (provided that the test does not reject the actual data-generating process). Natural ways...
-
作者：Ding, Yichuan; Wolkowicz, Henry
作者单位：Stanford University; University of Waterloo
摘要：The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of th...
-
作者：Conforti, Michele; Di Summa, Marco; Eisenbrand, Friedrich; Wolsey, Laurence A.
作者单位：University of Padua; Universite Catholique Louvain; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of checking nonemptiness of a set of this type is NP-complete, even in the case in which the linear system describes mixed-integer network flows with half-integral requirement on the nodes. This is in contrast to the case in which A is totally u...
-
作者：Huh, Woonghee Tim; Rusmevichientong, Paat
作者单位：Columbia University; Cornell University
摘要：We study stochastic inventory planning with lost sales and instantaneous replenishment where, contrary to the classical inventory theory, knowledge of the demand distribution is not available. Furthermore, we observe only the sales quantity in each period and lost sales are unobservable, that is, demand data are censored. The manager must make an ordering decision in each period based only on historical sales data. Excess inventory is either perishable or carried over to the next period. In th...
-
作者：Glazebrook, K. D.; Minty, R.
作者单位：Lancaster University
摘要：We generalise classical multiarmed bandits to allow for the distribution of a (fixed amount of a) divisible resource among the constituent bandits at each decision point. Bandit activation consumes amounts of the available resource, which may vary by bandit and state. Any collection of bandits may be activated at any decision epoch, provided they do not consume more resource than is available. We propose suitable bandit indices that reduce to those proposed by Gittins [Gittins, J. C. 1979. Ban...
-
作者：Cominetti, Roberto; Piazza, Adriana
作者单位：Universidad de Chile; Universidad de Chile
摘要：We study the long-term behavior of the optimal harvesting policies for a mixed forest composed by multiple species of different maturity ages. This model is a prototype for the exploitation of a finite resource such as land or space, which can be allocated to different activities that produce their revenue after certain delays at which the resource is liberated for reuse. We prove the existence and uniqueness of a sustainable state, and we discuss the conditions under which an optimal trajecto...
-
作者：Halman, Nir; Klabjan, Diego; Mostagir, Mohamed; Orlin, Jim; Simchi-Levi, David
作者单位：Massachusetts Institute of Technology (MIT); Hebrew University of Jerusalem; Northwestern University; California Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：The single-item stochastic inventory control problem is to find an inventory replenishment policy in the presence of independent discrete stochastic demands under periodic review and finite time horizon. In this paper, we prove that this problem is intractable and design for it a fully polynomial-time approximation scheme.
-
作者：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.
-
作者：Nascimento, Juliana M.; Powell, Warren B.
作者单位：Princeton University
摘要：We consider a multistage asset acquisition problem where assets are purchased now, at a price that varies randomly over time, to be used to satisfy a random demand at a particular point in time in the future. We provide a rare proof of convergence for an approximate dynamic programming algorithm using pure exploitation, where the states we visit depend on the decisions produced by solving the approximate problem. The resulting algorithm does not require knowing the probability distribution of ...
