-
作者：Chen, Rui; Gunluk, Oktay; Lodi, Andrea
作者单位：Cornell University
摘要：Dantzig-Wolfe (DW) decomposition is a well-known technique in mixedinteger programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. More precisely, we generate one cut for each DW block, and when combined with the constraints in the original formulation, these cuts imply the objectiv...
-
作者：Zhen, Jianzhe; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：Robust optimization and distributionally robust optimization are modeling paradigms for decision making under uncertainty where the uncertain parameters are only known to reside in an uncertainty set or are governed by any probability distribution from within an ambiguity set, respectively, and a decision is sought that minimizes a cost function under the most adverse outcome of the uncertainty. In this paper, we develop a rigorous and general theory of robust and distributionally robust nonli...
-
作者：Curmei, Mihaela; Hall, Georgina
作者单位：University of California System; University of California Berkeley; INSEAD Business School
摘要：We present a hierarchy of semidefinite programs (SDPs) for the problem of fitting a shape-constrained (multivariate) polynomial to noisy evaluations of an unknown shape-constrained function. These shape constraints include convexity or monotonicity over a box. We show that polynomial functions that are optimal to any fixed level of our hierarchy form a consistent estimator of the underlying shape-constrained function. As a by-product of the proof, we establish that sum of squares-convex polyno...
-
作者：Vardi, Shai; Haskell, William
作者单位：Purdue University System; Purdue University
摘要：Scarce resources are often shared between different stakeholders and need to be scheduled fairly among them. In this paper, we study the utility loss resulting from requiring the schedule to be fair, using the price of fairness-the ratio of the utility attainable with and without fairness restrictions. We focus on envy-freeness, an intuitive and well-studied fairness notion. We derive tight bounds on the price of fairness as a function of the problem parameters: the number of agents, the time ...
-
作者：Bai, Yicheng; Feldman, Jacob; Topaloglu, Huseyin; Wagner, Laura
作者单位：Washington University (WUSTL); University of Navarra; IESE Business School
摘要：We study assortment optimization problems under a natural variant of the multinomial logit model where the customers are willing to focus only on a certain number of products that provide the largest utilities. In particular, each customer has a rank cutoff, characterizing the number of products that she will focus on during the course of her choice process. Given that we offer a certain assortment of products, the choice process of a customer with rank cutoff k proceeds as follows. The custom...
-
作者：Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis
作者单位：University of Washington; University of Washington Seattle
摘要：For some epsilon > 10(-36), we give a randomized 3/2 - epsilon approximation algorithm for metric TSP.
-
作者：Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin
作者单位：University of Pennsylvania; Carnegie Mellon University; University of Pennsylvania
摘要：This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider gamma-discounted infinite-horizon Markov decision processes (MDPs) with state space S and action space A. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy has yet to be determined. In particular, all prior results suffer from a severe sample size barrier...
-
作者：Adler, Nicole; Olesen, Ole Bent; Volta, Nicola
作者单位：Hebrew University of Jerusalem; University of Southern Denmark; Cranfield University
摘要：Horizontal mergers and acquisitions offer firms the means to grow. However, forecasting these actions' potential effects on the market is not a simple task. We propose a model that identifies optimal horizontal merger configurations for an industry. The model endogenizes the merger choice by maximizing the overall potential efficiency gain at the level of an industry or firm with multiple branches. We further extend the model to consider mergers that create contiguous firms, should network eff...
-
作者：Lo, Andrew W.; Wu, Lan; Zhang, Ruixun; Zhao, Chaoyi
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); The Santa Fe Institute; Peking University; Peking University; Peking University; Peking University
摘要：We develop a mathematical framework for constructing optimal impact portfolios and quantifying their financial performance by characterizing the returns of impactranked assets using induced order statistics and copulas. The distribution of induced order statistics can be represented by a mixture of order statistics and uniformly distributed random variables, where the mixture function is determined by the dependence structure between residual returns and impact factors-characterized by copulas...
-
作者：Light, Bar; Johari, Ramesh; Weintraub, Gabriel
作者单位：Tel Aviv University; Stanford University; Stanford University
摘要：Online platforms collect rich information about participants and then share some of this information back with them to improve market outcomes. In this paper, we study the following information disclosure problem in two-sided markets: if a platform wants to maximize revenue, which sellers should the platform allow to participate, and how much of its available information about participating sellers' quality should the platform share with buyers? We study this information disclosure problem in ...
