-
作者：Afeche, Philipp; Caldentey, Rene; Gupta, Varun
作者单位：University of Toronto; University of Chicago
摘要：We consider a multiclass multiserver queueing system and study the problem of designing an optimal matching topology (or service compatibility structure) between customer classes and servers under a first come first served-assign longest idle server (FCFS-ALIS) service discipline. Specifically, we are interested in finding matching topologies that optimize-in a Pareto efficiency sense-the trade-off between two competing objectives: (i) minimizing customers' waiting time delays and (ii) maximiz...
-
作者：Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
作者单位：Columbia University; Stanford University; Harvard University
摘要：In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive....
-
作者：Poursoltani, Mehran; Delage, Erick
作者单位：Universite de Montreal; HEC Montreal; Universite de Montreal; HEC Montreal
摘要：This paper explores the idea that two-stage worst-case regret minimization problems with either objective or right-hand side uncertainty can be reformulated as two-stage robust optimization problems and can therefore benefit from the solution schemes and theoretical knowledge that have been developed in the last decade for this class of problems. In particular, we identify conditions under which a first-stage decision can be obtained either exactly using popular adjustable robust optimization ...
-
作者：Brown, David B.; Zhang, Jingwei
作者单位：Duke University
摘要：We consider a sequential decision problem involving shared resources and signals in which a decision maker repeatedly observes some exogenous information (the signal), modeled as a finite-state Markov process, then allocates a limited amount of a shared resource across a set of projects. The framework includes a number of applications and generalizes Markovian multiarmed bandit problems by (a) incorporating exogenous information through the signal and (b) allowing for more general resource all...
-
作者：Ghuge, Rohan; Kwon, Joseph; Nagarajan, Viswanath; Sharma, Adetee
作者单位：University of Michigan System; University of Michigan
摘要：Y We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, cardinality-constrained, and knapsack-constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and suitable linear-program rounding algorithms. We obtain a randomized polynomial time approximation sc...
-
作者：Lam, Henry; Qian, Huajie
作者单位：Columbia University
摘要：In stochastic simulation, input uncertainty refers to the output variability arising from the statistical noise in specifying the input models. This uncertainty can be measured by a variance contribution in the output, which, in the nonparametric setting, is commonly estimated via the bootstrap. However, due to the convolution of the simulation noise and the input noise, the bootstrap consists of a two-layer sampling and typically requires substantial simulation effort. This paper investigates...
-
作者：Cen, Shicong; Cheng, Chen; Chen, Yuxin; Wei, Yuting; Chi, Yuejie
作者单位：Carnegie Mellon University; Stanford University; Princeton University; University of Pennsylvania
摘要：Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization-an algorithmic scheme that encourages exploration-and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develop...
-
作者：Li, Xiaocheng; Ye, Yinyu
作者单位：Imperial College London; Stanford University
摘要：We study an online linear programming (OLP) problem under a random input model in which the columns of the constraint matrix along with the corresponding coefficients in the objective function are independently and identically drawn from an unknown distribution and revealed sequentially over time. Virtually all existing online algorithms were based on learning the dual optimal solutions/prices of the linear programs (LPs), and their analyses were focused on the aggregate objective value and so...
-
作者：Banerjee, Siddhartha; Freund, Daniel; Lykouris, Thodoris
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：Optimizing shared vehicle systems (bike-/scooter-/car-/ride-sharing) are more challenging compared with traditional resource allocation settings because of the presence of complex network externalities-changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using such models to design pricing and other...
-
作者：Mittal, Areesh; Hanasusanto, Grani A.
作者单位：University of Texas System; University of Texas Austin
摘要：We study the problem of finding the Liiwner-John ellipsoid (i.e., an ellipsoid with minimum volume that contains a given convex set). We reformulate the problem as a generalized copositive program and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, when the underlying set is a polytope, our method never provides an ellipsoid of higher volume than the one obtained by sc...
