-
作者：Ozkan, Erhun
作者单位：Koc University
摘要：A fork-join processing network is a queueing network in which tasks associated with a job can be processed simultaneously. Fork-join processing networks are prevalent in computer systems, healthcare, manufacturing, project management, justice systems, and so on. Unlike the conventional queueing networks, fork-join processing networks have synchronization constraints that arise because of the parallel processing of tasks and can cause significant job delays. We study scheduling in fork-join pro...
-
作者：Amini, Hamed; Minca, Andreea; Sulem, Agnes
作者单位：University System of Georgia; Georgia State University; Cornell University
摘要：We introduce threshold growth in the classical threshold contagion model, or equivalently a network of Cramer-Lundberg processes in which nodes have downward jumps when there is a failure of a neighboring node. Choosing the configuration model as underlying graph, we prove fluid limits for the baseline model, as well as extensions to the directed case, state-dependent interarrival times and the case of growth driven by upward jumps. We obtain explicit ruin probabilities for the nodes according...
-
作者：Harshaw, Christopher; Kazemi, Ehsan; Feldman, Moran; Karbasi, Amin
作者单位：Yale University; Alphabet Inc.; Google Incorporated; University of Haifa; Yale University; Yale University
摘要：We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SAMPLEGREEDY, which obtains a (p + 2 + o(1))-...
-
作者：Correa, Jose; Cristi, Andres; Oosterwijk, Tim
作者单位：Universidad de Chile; Vrije Universiteit Amsterdam
摘要：Dynamic network flows, or network flows over time, constitute an important model for real-world situations in which steady states are unusual, such as urban traffic and the internet. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this paper, we study dynamic equilibria in the deterministic fluid queuing model in single-source, single-sink networks-arguably the most basic model for flows over time. In the last decade, we h...
-
作者：Yu, Huizhen
作者单位：University of Alberta
摘要：We consider the linear programming approach for constrained and unconstrained Markov decision processes (MDPs) under the long-run average-cost criterion, where the class of MDPs in our study have Borel state spaces and discrete countable action spaces. Under a strict unboundedness condition on the one-stage costs and a recently introduced majorization condition on the state transition stochastic kernel, we study infinite-dimensional linear programs for the average-cost MDPs and prove the absen...
-
作者：Kim, Daehyun; Li, Xiaoxi
作者单位：Wuhan University
摘要：This paper defines a general framework to study infinitely repeated games with time-dependent discounting in which we distinguish and discuss both time-consistent and -inconsistent preferences. To study the long-term properties of repeated games, we introduce an asymptotic condition to characterize the fact that players become more and more patient; that is, the discount factors at all stages uniformly converge to one. Two types of folk theorems are proven without the public randomization assu...
-
作者：Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Philip
作者单位：University of Liverpool; University of Erlangen Nuremberg; Sapienza University Rome
摘要：We study the trade-off between the price of anarchy (PoA) and the price of stability (PoS) in mechanism design in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to these metrics and observe that two fundamental mechanisms, namely the first price (FP) and the second price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely char...
-
作者：He, Taotao; Tawarmalani, Mohit
作者单位：Shanghai Jiao Tong University; Purdue University System; Purdue University
摘要：In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P, where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes O(dnlogd) time, where d is the number of inner function...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University
摘要：A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization....
-
作者：Correa, Jose; Dutting, Paul; Fischer, Felix; Schewior, Kevin
作者单位：Universidad de Chile; University of London; London School Economics & Political Science; University of London; Queen Mary University London; University of Cologne
摘要：A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables. given a sequence of random variables X-1, . . . , X-n drawn independently from the same distribution, the goal is to choose a stopping time tau such that for the maximum value of alpha and for all distributions, E[X-tau] >= alpha center dot E[max X-t(t)]. What makes this problem challenging is that the decision whether tau = t may only depen...
