-
作者：Rostami, Borzou; Errico, Fausto; Lodi, Andrea
作者单位：Wilfrid Laurier University; Universite de Montreal; Polytechnique Montreal; University of Quebec; Ecole de Technologie Superieure - Canada; Cornell University
摘要：In this paper, we propose a general modeling and solving framework for a large class of binary quadratic programs subject to variable partitioning constraints. Problems in this class have a wide range of applications as many binary quadratic programs with linear constraints can be represented in this form. By exploiting the structure of the partitioning constraints, we propose mixed-integer nonlinear programming (MINLP) and mixedinteger linear programming (MILP) reformulations and show the rel...
-
作者：Goyal, Vineet; Grand-Clement, Julien
作者单位：Columbia University
摘要：Markov decision processes (MDPs) are used to model stochastic systems in many applications. Several efficient algorithms to compute optimal policies have been studied in the literature, including value iteration (VI) and policy iteration. However, these do not scale well, especially when the discount factor for the infinite horizon discounted reward, lambda, gets close to one. In particular, the running time scales as O (1=(1 - lambda)) for these algorithms. In this paper, our goal is to desig...
-
作者：Liu, Junyi; Pang, Jong-Shi
作者单位：Tsinghua University; University of Southern California
摘要：This paper proposes the use of a variant of the conditional value-at-risk (CVaR) risk measure, called the interval conditional value-at-risk (In-CVaR), for the treatment of outliers in statistical learning by excluding the risks associated with the left and right tails of the loss. The risk-based robust learning task is to minimize the In-CVaR risk measure of a random functional that is the composite of a piecewise affine loss function with a potentially nonsmooth difference-of-convex statisti...
-
作者：Shi, Yun; Cui, Xiangyu; Zhou, Xun Yu
作者单位：East China Normal University; Shanghai Institute of International Finance & Economics; Shanghai University of Finance & Economics; Columbia University; Columbia University
摘要：The security market line is often flat or downward-sloping. We hypothesize that probability weighting plays a role and one ought to differentiate between periods in which agents overweight extreme events and those in which they underweight them. Overweighting inflates the probability of extremely bad events and demands greater compensation for beta risk, whereas underweighting does the opposite. Unconditional on probability weighting, these two effects offset each other, resulting in a flat or...
-
作者：Gao, Yuan; Kroer, Christian
作者单位：Columbia University
摘要：Linear Fishermarkets are a fundamental economicmodelwith diverse applications. In the finite-dimensional case of n buyers and m items, amarket equilibriumcan be computed using the celebrated Eisenberg-Gale convex program. Motivated by large-scale Internet advertising and fair division applications, we consider a generalization of a linear Fisher market where there is a finite set of buyers and ameasurable itemspace. We introduce generalizations of the Eisenberg-Gale convex program and its dual...
-
作者：Garg, Jugal; Vegh, Laszlo A.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of London; London School Economics & Political Science
摘要：We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly polynomial Duan-Mehlhorn (DM) algorithm. We use the DMalgorithm as a subroutine to identify revealed edges-that is, pairs of agents and goods that must correspond to the best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if ther...
-
作者：Liang, Jinpeng; Lyu, Guodong; Teo, Chung-Piaw; Gao, Ziyou
作者单位：Dalian Maritime University; Hong Kong University of Science & Technology; National University of Singapore; National University of Singapore; Beijing Jiaotong University
摘要：Crowd management during peak commuting hours is a key challenge facing oversaturated metro systems worldwide, which results in serious safety concerns and uneven service experience for commuters on different origin-destination (o-d) pairs. This paper develops realtime passenger flow control policies to manage the inflow of crowds at each station, to optimize the total load carried or revenue earned (efficiency), and to ensure that adequate service is provided to passengers on each o-d pair (fa...
-
作者：Duchi, John; Hashimoto, Tatsunori; Namkoong, Hongseok
作者单位：Stanford University; Stanford University; Stanford University; Columbia University
摘要：While modern large-scale data sets often consist of heterogeneous subpopulations-for example, multiple demographic groups or multiple text corpora-the standard practice of minimizing average loss fails to guarantee uniformly low losses across all sub-populations. We propose a convex procedure that controls the worst case performance over all subpopulations of a given size. Our procedure comes with finite-sample (nonparametric) convergence guarantees on the worst-off subpopulation. Empirically,...
-
作者：Nakahira, Yorie; Ferragut, Andres; Wierman, Adam
作者单位：Carnegie Mellon University; University ORT Uruguay; California Institute of Technology
摘要：Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, unpredictability and instability in service capacity often incur operational and infrastructural costs. In this paper, we seek to characterize optimal distributed algorithms that maximize the predictability, stability, or both when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes both the stationary mean and variance of the service...
-
作者：Hmedi, Hassan; Arapostathis, Ari; Pang, Guodong
作者单位：University of Texas System; University of Texas Austin; Rice University
摘要：We introduce a system-wide safety staffing (SWSS) parameter for multiclass multipool networks of any tree topology, Markovian or non-Markovian, in the Halfin-Whitt regime. This parameter can be regarded as the optimal reallocation of the capacity fluctuations (positive or negative) of order root n when each server pool uses a square-root staffing rule. We provide an explicit formof the SWSS as a function of the systemparameters, which is derived using a graph theoretic approach based on Gaussi...
