-
作者：Scully, Ziv; van Kreveld, Lucas
作者单位：Cornell University; Eindhoven University of Technology
摘要：We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the Gittins policy minimizes mean response time in this setting. However, the behavior of the tail of response time under Gittins is poorly understood, even in the largeresponse -time limit. Characterizing Gittins's asymptotic tail behavior is important because if Gittins has optimal tail asymptotics, then it simultaneously provides optimal mean response time and good tail performance. In this work, we give the ...
-
作者：Yang, Shuoguang; Fang, Ethan X.; Shanbhag, Uday V.
作者单位：Hong Kong University of Science & Technology; Duke University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：As systems grow in size, scale, and intricacy, the challenges of misspecification become even more pronounced. In this paper, we focus on parametric misspecification in regimes complicated by risk and nonconvexity. When this misspecification may be resolved via a parallel learning process, we develop data -driven schemes for resolving a broad class of misspecified stochastic compositional optimization problems. Notably, this rather broad class of compositional problems can contend with challen...
-
作者：Akchen, Yi-Chun; Misic, Velibor V.
作者单位：University of London; University College London; University of California System; University of California Los Angeles
摘要：We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Because enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging because of the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a...
-
作者：Bertsimas, Dimitris; Paskov, Alex
作者单位：Massachusetts Institute of Technology (MIT)
摘要：In this paper, we propose and scale a framework based on exact dynamic programming to solve the game of Wordle, which has withstood many attempts to be solved by a variety of methods ranging from reinforcement learning to information theory. First, we derive a mathematical model of the game, present the resultant Bellman equation, and outline a series of optimizations to make this approach tractable. We then outline how to extend the framework to solve variants of the game-such as Wordle Hard ...
-
作者：Yang, Shuoguang; Li, Xudong; Lan, Guanghui
作者单位：Hong Kong University of Science & Technology; Fudan University; University System of Georgia; Georgia Institute of Technology
摘要：Attention to data-driven optimization approaches, including the well-known stochastic gradient descent method, has grown significantly over recent decades, but data driven constraints have rarely been studied because of the computational challenges of projections onto the feasible set defined by these hard constraints. In this paper, we focus on the nonsmooth convex-concave stochastic minimax regime and formulate the data-driven constraints as expectation constraints. The minimax expectation c...
-
作者：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...
-
作者：Bichler, Martin; Fichtl, Max; Oberlechner, Matthias
作者单位：Technical University of Munich
摘要：Auctions are modeled as Bayesian games with continuous type and action spaces. Determining equilibria in auction games is computationally hard in general, and no exact solution theory is known. We introduce an algorithmic framework in which we discretize type and action space and then learn distributional strategies via online optimization algorithms. One advantage of distributional strategies is that we do not have to make any assumptions on the shape of the bid function. Besides, the expecte...
-
作者：Glasserman, Paul; Li, Mike
作者单位：Columbia University
摘要：We study the behavior of linear discriminant functions for binary classification in the infinite-imbalance limit, where the sample size of one class grows without bound while the sample size of the other remains fixed. The coefficients of the classifier minimize an empirical loss specified through a weight function. We show that for a broad class of weight functions, the intercept diverges but the rest of the coefficient vector has a finite almost sure limit under infinite imbalance, extending...
-
作者：Chan, Timothy C. Y.; Mahmood, Rafid; Zhu, Ian Yihang
作者单位：University of Toronto; University of Ottawa; National University of Singapore
摘要：Inverse optimization describes a process that is the reverse of traditional mathematical optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines objective and/or constraint parameters that render these decisions approximately or exactly optimal. In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. This ...
-
作者：Balcan, Maria-Florina; Sandholm, Tuomas; Vitercik, Ellen
作者单位：Carnegie Mellon University; Stanford University; Stanford University
摘要：We study multi-item profit maximization when there is an underlying distribution over buyers' values. In practice, a full description of the distribution is typically unavailable, so we study the setting where the mechanism designer only has samples from the distribution. If the designer uses the samples to optimize over a complex mechanism class- such as the set of all multi-item, multibuyer mechanisms-a mechanism may have high average profit over the samples, but low expected profit. This ra...
