-
作者：Bo, Lijun; Huang, Yijie; Yu, Xiang
作者单位：Xidian University; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Hong Kong Polytechnic University
摘要：This paper studies stochastic control problems motivated by optimal consumption with wealth benchmark tracking. The benchmark process is modeled by a combination of a geometric Brownian motion and a running maximum process, indicating its increasing trend in the long run. We consider a relaxed tracking formulation such that the wealth compensated by the injected capital always dominates the benchmark process. The stochastic control problem is to maximize the expected utility of consumption ded...
-
作者：Happach, Felix; Schulz, Andreas S.
作者单位：Technical University of Munich; Technical University of Munich
摘要：We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also mak...
-
作者：Jin, Ying; Yang, Zhuoran; Wang, Zhaoran
作者单位：Harvard University; Yale University; Northwestern University
摘要：We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a data set collected a priori. Because of the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the data set, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply fl...
-
作者：Muthukumar, Vidya; Phade, Soham; Sahai, Anant
作者单位：University System of Georgia; Georgia Institute of Technology; University of California System; University of California Berkeley
摘要：We study the limiting behavior of the mixed strategies that result from optimal no-regret learning in a repeated game setting where the stage game is any 2 x 2 competitive game. We consider optimal no-regret algorithms that are mean-based and monotonic in their argument. We show that for any such algorithm, the limiting mixed strategies of the players cannot converge almost surely to any Nash equilibrium. This negative result is also shown to hold under a broad relaxation of these assumptions,...
-
作者：Storm, Jaap; Berkelmans, Wouter; Bekker, Rene
作者单位：Eindhoven University of Technology; Vrije Universiteit Amsterdam
摘要：We consider a many-server queue in which each server can serve multiple customers in parallel. Such multitasking phenomena occur in various applications areas (e.g., in hospitals and contact centers), although the impact of the number of customers who are simultaneously served on system efficiency may vary. We establish diffusion limits of the queueing process under the quality-and-efficiency-driven scaling and for different policies of assigning customers to servers depending on the number of...
-
作者：Naegele, Martin; Santiago, Richard; Zenklusen, Rico
作者单位：University of Bonn
摘要：A long-standing open question in integer programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{c(inverted perpendicular)x : Tx <= b, gamma(inverted perpendicular)x = r (mod m), x is an element of Z(n)} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm...
-
作者：Aprile, Manuel; Conforti, Michele; Di Summa, Marco
作者单位：University of Padua
摘要：A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variab...
-
作者：Haasler, Isabel; Ringh, Axel; Chen, Yongxin; Karlsson, Johan
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Chalmers University of Technology; University of Gothenburg; University System of Georgia; Georgia Institute of Technology; Royal Institute of Technology
摘要：In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropyregularized...
-
作者：Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：In this paper, we consider a semidefinite programming (SDP) relaxation of the quadratic knapsack problem. After applying low-rank factorization, we get a nonconvex problem, whose feasible region is an algebraic variety with certain good geometric properties, which we analyze. We derive a rank condition under which these two formulations are equivalent. This rank condition is much weaker than the classical rank condition if the coefficient matrix has certain special structures. We also prove th...
-
作者：Gnoatto, Alessandro; Lavagnini, Silvia; Picarelli, Athena
作者单位：University of Verona; BI Norwegian Business School
摘要：We propose a novel computational procedure for quadratic hedging in highdimensional incomplete markets, covering mean-variance hedging and local risk minimization. Starting from the observation that both quadratic approaches can be treated from the point of view of backward stochastic differential equations (BSDEs), we (recursively) apply a deep learning-based BSDE solver to compute the entire optimal hedging strategies paths. This allows us to overcome the curse of dimensionality, extending t...
