-
作者：Zhao, Zhisheng; Banerjee, Sayan; Mukherjee, Debankur
作者单位：University System of Georgia; Georgia Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：Join-the-shortest queue (JSQ) is a classical benchmark for the performance of parallel-server queueing systems because of its strong optimality properties. Recently, there has been significant progress in understanding its large-system asymptotic behavior. In this paper, we analyze the JSQ policy in the super-Halfin-Whitt scaling window when load per server scales with the system size N as lim(->infinity) (1 - ) = for is an element of (1/2, 1) and > 0. We establish that the centered and scaled...
-
作者：Cembrano, Javier; Fischer, Felix; Klimm, Max
作者单位：Max Planck Society; Technical University of Berlin; University of London; Queen Mary University London
摘要：A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and alpha-optimal if the expected number of nominations received by the selected individual is always at least alpha times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is 1/2-optimal, and this is the bes...
-
作者：Jiang, Jiashuo; Ma, Will; Zhang, Jiawei
作者单位：Hong Kong University of Science & Technology; Columbia University; New York University
摘要：Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some ingenuity. In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds ...
-
作者：Goenka, Ritesh; Gupta, Eashan; Khyalia, Sushil; Kalyanakrishnan, Shivaram
作者单位：University of Oxford; University of Illinois System; University of Illinois Urbana-Champaign; Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：Policy iteration (PI) is a widely used family of algorithms to compute optimal policies for Markov decision problems (MDPs). Howard's [Howard RA (1960) Dynamic Programming and Markov Processes (MIT Press, Cambridge, MA)] PI is one of the most commonly used algorithms from this family. Despite its popularity, theoretical analysis of the running-time complexity of Howard's PI has remained elusive. For n-state, two-action MDPs, the best known lower and upper bounds are ohm(n) and O(2n/n) iteratio...
-
作者：Jhunjhunwala, Prakirt R.; Zubeldia, Martin; Maguluri, Siva Theja
作者单位：Columbia University; University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology
摘要：We consider a load-balancing system composed of a fixed number of singleserver queues operating under the well-known join-the-shortest queue policy and where jobs/customers are impatient and abandon if they do not receive service after some (random) amount of time. In this setting, we characterize the centered and appropriately scaled steady-state queue-length distribution (hereafter referred to as limiting distribution) in the limit as the abandonment rate goes to zero at the same time as the...
-
作者：Kang, Weining
作者单位：University System of Maryland; University of Maryland Baltimore County
摘要：In this paper, under mild conditions on the arrival, service, and patience time distributions, we establish the well-posedness of the fluid model of a multiclass manyserver queueing model with differentiated service and patience times operated under the global FCFS service discipline. In particular, the well-posedness of the fluid model is established through the study of the existence and uniqueness of fixed points of a certain functional map of Volterra type. In addition, by showing a local ...
-
作者：Christodoulou, George; Fiat, Amos; Koutsoupias, Elias; Sgouritsa, Alkmini
作者单位：Aristotle University of Thessaloniki; Tel Aviv University; University of Oxford; Athens University of Economics & Business
摘要：We study envy-freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore, that it ...
-
作者：Cerny, Ales; Ruf, Johannes; Schweizer, Martin
作者单位：University of London; London School Economics & Political Science; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Monotone mean-variance (MMV) utility is the minimal modification of the classical Markowitz mean-variance (MV) utility that respects rational ordering of investment opportunities. This paper provides, for the first time, a complete characterization of optimal dynamic portfolio choice for the MMV utility in asset price models with independent returns. The task is performed under minimal assumptions, weaker than the existence of an equivalent martingale measure and with no restrictions on the mo...
-
作者：Olikier, Guillaume; Gallivan, Kyle A.; Absil, P. -A.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; State University System of Florida; Florida State University; Universite Catholique Louvain
摘要：This paper considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the algebraic variety of real matrices of upperbounded rank. This problem is known to enable the formulation of various machine learning or signal processing tasks such as dimensionality reduction, collaborative filtering, and signal recovery. Several definitions of stationarity exist for this nonconvex problem. Among them, Bouligand stationarity is the strongest necessary con...
-
作者：Renaud, Jean-Francois; Roch, Alexandre; Simard, Clarence
作者单位：University of Quebec; University of Quebec Montreal; University of Quebec; University of Quebec Montreal
摘要：We study an optimal stochastic control problem in which a firm's cash/surplus process is controlled by dividend payments and capital injections. We consider absolutely continuous dividend policies subject to a level-dependent upper bound on the dividend rate and general capital injection strategies. We construct an optimal solution for which either the optimal capital injections consist of a forced bailout strategy when the cash process reaches zero or no injection of capital is ever made and ...
