-
作者：Li, Xiang; Liang, Jiadong; Chen, Xinyun; Zhang, Zhihua
作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen
摘要：Stream stochastic gradient descent (SGD) is a simple and efficient method for solving online optimization problems in operations research (OR), where data are generated by parameter-dependent Markov chains. Unlike traditional approaches which require increasing batch sizes during iterations, stream SGD uses a single sample per iteration, significantly improving sample efficiency. This paper establishes a systematic framework for analyzing stream SGD, leveraging the Poisson equation solution to...
-
作者：Behdin, Kayhan; Chen, Wenyu; Mazumder, Rahul
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model, which is a key problem in statistical machine learning. Given n samples from a multivariate Gaussian distribution with p variables, the goal is to estimate the p x p inverse covariance matrix (aka precision matrix), assuming it is sparse (i.e., has a few nonzero entries). We propose GraphL0BnB, a new estimator based on an & euro;0-penalized version of the pseudo-likelihood function; most earli...
-
作者：Prokopyev, Oleg A.; Ralphs, Ted K.
作者单位：University of Zurich; Lehigh University
摘要：We consider the computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader's perspective. We show that, for any constant c > 0, the problem of finding a leader's solution that is within Euclidean distance c(n) of any locally optimal leader's solution, where n is the total number of variables, is NP-hard. Our derivations exploit techniques similar to those used for the analogous result for quadratic optimization problems (QPs). ...
-
作者：Zhou, Ziyan; Wang, Tong; Zhang, Tingwei
作者单位：Shanghai Jiao Tong University; City University of Hong Kong; The Chinese University of Hong Kong, Shenzhen
摘要：Stockout-based substitution creates complex stochastic dynamics in inventory systems even in highly symmetric settings. We study a joint assortment and inventory allocation problem in which a firm allocates a fixed total inventory of m units across n perfectly substitutable product types (e.g., colors or designs). Customers are indifferent among available types and arrive sequentially, each purchasing one unit chosen uniformly at random from the nonempty types. The sales process terminates whe...
-
作者：Benade, Gerdus; Procaccia, Ariel D.; Tucker-Foltz, Jamie
作者单位：Boston University; Harvard University; Yale University
摘要：The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee partisan fairness. We aim to have the best of both worlds by optimizing an objective subject to a binary fairness constraint. As a fairness constraint, we adopt the geometric target, which requires the number of seats won by each party to be at least the average (rounded down) of its out...
-
作者：Najafi, Sajjad; Jasin, Stefanus; Uichanco, Joline; Zhao, Jinglong
作者单位：Hautes Etudes Commerciales (HEC) Paris; University of Michigan System; University of Michigan; New York University; New York University Tandon School of Engineering; Boston University
摘要：We study assortment and price optimization under the contextual concavity (CC) model introduced in the literature, which subsumes the well-known multiattribute loss aversion (MLA) model. Unlike context-independent choice models that assume product utilities are unaffected by other alternatives in the assortment, the CC model offers a context-dependent framework that incorporates reference points across multiple attributes and captures prominent context effects (e.g., the compromise effect) wel...
-
作者：Charlet, Nils; Van Houdt, Benny
作者单位：University of Antwerp
摘要：Recently it was shown that the response time of first-come-first-served (FCFS) scheduling can be stochastically and asymptotically improved upon by the Nudge scheduling algorithm in case of light-tailed job size distributions. Such improvements are feasible even when the jobs are partitioned into two types, and the scheduler only has information about the type of incoming jobs (but not their size). In this paper, we introduce Nudge*(M) scheduling, where basically any incoming type 1 job is all...
-
作者：Jia, Su; Li, Andrew; Ravi, R.; Oli, Nishant; Duff, Paul; Anderson, Ian
作者单位：Amazon.com; Carnegie Mellon University
摘要：Modern platforms leverage randomized experiments to make informed decisions from a given set of items (treatment arms). As a particularly challenging scenario, these items can (i) arrive in a high volume, with thousands of new items being released per hour, and (ii) have a short lifetime due to their transient nature. We study a Bayesian multiple-play bandit problem that encapsulates the key features of this scenario. In each round, a set of arms arrives. Each arm has a lifetime w and an unkno...
-
作者：Jiang, Songchen; Li, Zhaolin; Bi, Sheng; Teo, Chung-Piaw; Huang, Min
作者单位：Northeastern University - China; National University of Singapore; University of Sydney; Shanghai University of Finance & Economics
摘要：We generalize Scarf's classical min-max newsvendor model from a singleperiod setting to a multiperiod inventory system with independent demand across periods. This extension leverages mean-variance analysis to capture the dynamic effects of lead times, yielding closed-form expressions for the optimal base-stock level. As a concrete application, we study a single-product, dual-sourcing system with constant lead times and backlogging. We show that the optimal tailored base-surge policy admits a ...
