-
作者：Aouad, Ali; Segev, Danny
作者单位：University of London; London Business School; Tel Aviv University
摘要：We study the incremental knapsack problem, where one wishes to sequentially pack items into a knapsack whose capacity expands over a finite planning horizon, with the objective of maximizing time-averaged profits. Although various approximation algorithms were developed under mitigating structural assumptions, obtaining nontrivial performance guarantees for this problem in its utmost generality has remained an open question thus far. In this paper, we devise a polynomial-time approximation sch...
-
作者：Mazumder, Rahul; Radchenko, Peter; Dedieuc, Antoine
作者单位：Massachusetts Institute of Technology (MIT); University of Sydney
摘要：We study a seemingly unexpected and relatively less understood overfitting aspect of a fundamental tool in sparse linear modeling-best subset selection-which minimizes the residual sum of squares subject to a constraint on the number of nonzero coefficients. Whereas the best subset selection procedure is often perceived as the gold standard in sparse learning when the signal-to-noise ratio (SNR) is high, its predictive performance deteriorates when the SNR is low. In particular, it is outperfo...
-
作者：Balseiro, Santiago R.; Lu, Haihao; Mirrokni, Vahab
作者单位：Columbia University; Alphabet Inc.; Google Incorporated; University of Chicago
摘要：Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the r...
-
作者：Kremer, Mirko; de Vericourt, Francis
作者单位：Frankfurt School Finance & Management; European School of Management & Technology
摘要：To study the effect of congestion on the fundamental tradeoff between diagnostic accuracy and speed, we empirically test the predictions of a formal sequential testing model in a setting where the gathering of additional information can improve diagnostic accuracy but may also take time and increase congestion as a result. The efficient management of such systems requires a careful balance of congestion-sensitive stopping rules. These include diagnoses made based on very little or no diagnosti...
-
作者：Lamas-Fernandez, Carlos; Bennell, Julia A.; Martinez-Sykora, Antonio
作者单位：University of Southampton; Solent University; University of Leeds
摘要：Research on the three-dimensional (3D) packing problem has largely focused on packing boxes for the transportation of goods. As a result, there has been little focus on packing irregular shapes in the operational research literature. New technologies have raised the practical importance of 3D irregular packing problems and the need for efficient solutions. In this work, we address the variant of the problem where the aim is to place a set of 3D irregular items in a container, while minimizing ...
-
作者：Zhang, Haixiang; Zheng, Zeyu; Lavaei, Javad
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We propose new sequential simulation???optimization algorithms for general convex optimization via simulation problems with high-dimensional discrete decision space. The performance of each choice of discrete decision variables is evaluated via stochastic simulation replications. If an upper bound on the overall level of uncertainties is known, our proposed simulation???optimization algorithms utilize the discrete convex structure and are guaranteed with high probability to find a solution tha...
-
作者：Hochbaum, Dorit S.; Levin, Asaf; Rao, Xu
作者单位：Technion Israel Institute of Technology
摘要：Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parame...
-
作者：Chen, Xi; Wang, Yining
作者单位：New York University; University of Texas System; University of Texas Dallas
摘要：This paper studies a dynamic pricing problem undermodel misspecification. To characterize model misspecification, we adopt the epsilon-contamination model-the most fundamental model in robust statistics and machine learning. In particular, for a selling horizon of length T, the online epsilon-contamination model assumes that demands are realized according to a typical unknown demand function only for (1 - epsilon)T periods. For the rest of epsilon T periods, an outlier purchase can happen with...
-
作者：Bertsimas, Dimitris; Mundru, Nishanth
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We propose a novel, optimization-based method that takes into account the objective and problem structure for reducing the number of scenarios, m, needed for solving two-stage stochastic optimization problems. We develop a corresponding convex optimization-based algorithm and show that, as the number of scenarios increase, the proposed method recovers the SAA solution. We report computational results with both synthetic and real-world data sets that show that the proposed method has significan...
-
作者：Chen, Gang; Gayon, Jean-Philippe; Lemaire, Pierre
作者单位：Guangzhou University; Universite Clermont Auvergne (UCA); Polytechnic Institute of Clermont Auvergne; Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; Mines Saint-Etienne; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：We consider a stochastic scheduling problem in clearing systems with two types of jobs, each characterized by a general service time distribution, an exponentially distributed lifetime, and a reward. A job abandons the system if its waiting time in the queue is larger than its lifetime. Preemption is not allowed. The objective is to maximize the total expected reward. When service times are homogeneous, we provide a set of necessary and sufficient conditions for the optimality of a strict prio...
