-
作者：Feldman, Moran; Liu, Paul; Norouzi-Fard, Ashkan; Svensson, Ola; Zenklusen, Rico
作者单位：University of Haifa; Stanford University; Alphabet Inc.; Google Incorporated; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are a single-pass streaming algorithm that uses Oe(k) memory and achieves an approxim...
-
作者：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 ...
-
作者：Zhao, Renbo
作者单位：University of Iowa
摘要：We present and analyze an away-step Frank-Wolfe method for the convex optimization problem minx is an element of Xf(Ax) + < c , x > , where f is a theta-logarithmically homogeneous self-concordant barrier, A is a linear operator that may be noninvertible, < c , > is a linear function, and X is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and total variationregularized Poisson image deblurring. We establish affin...
-
作者：Fujishie, Satoru; Yang, Zaifu
作者单位：Kyoto University; University of York - UK
摘要：We propose a novel strategy-proof dynamic auction for efficiently allocating heterogeneous indivisible commodities. The auction applies to all unimodular demand types of Baldwin and Klemperer's necessary and sufficient condition for the existence of competitive equilibrium which accommodate a wide variety of complements, substitutes, gross substitutes and complements, and any other kinds. Although bidders are not assumed to be price takers so they can act strategically, this auction induces bi...
-
作者：Brustle, Johannes; Correa, Jose; Dutting, Paul; Ezra, Tomer; Feldman, Michal; Verdugo, Victor
作者单位：Sapienza University Rome; Universidad de Chile; Harvard University; Tel Aviv University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the (1- E)-competition complexity of different types of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance is at least a (1 - E)-approximation to the expected off-line optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal an...
-
作者：Kunimoto, Takashi; Saran, Rene; Serrano, Roberto
作者单位：Singapore Management University; University System of Ohio; University of Cincinnati; Brown University
摘要：This is the brief corrigendum to Interim rationalizable implementation of functions [Kunimoto T, Saran R, Serrano R (2024) Interim rationalizable implementation of functions. Math. Oper Res. 49(3):1791-1824].
-
作者：Saldi, Naci
作者单位：Ihsan Dogramaci Bilkent University
摘要：In this paper, we introduce discrete-time linear mean-field games subject to an infinite-horizon discounted-cost optimality criterion. At every time, each agent is randomly coupled with another agent via their dynamics and one-stage cost function, where this randomization is generated via the empirical distribution of their states (i.e., the mean-field term). Therefore, the transition probability and the one-stage cost function of each agent depend linearly on the mean-field term, which is the...
-
作者：Cao, Shengyu; He, Simai; Wang, Zizhuo; Feng, Yifan
作者单位：University of Toronto; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen; National University of Singapore
摘要：We study an optimal server partition and customer assignment problem for an uncapacitated first-come-first-served queueing system with heterogeneous types of customers. Each type of customer is associated with a Poisson arrival, a certain service time distribution, and a unit waiting cost. The goal is to minimize the expected total waiting cost by partitioning the server into subqueues, each with a smaller service capacity, and routing customer types probabilistically. First, we show that by p...
