-
作者：Jaillet, Patrick; Lu, Xin
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 - 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117-126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and kno...
-
作者：Li, Yanjun
作者单位：Purdue University System; Purdue University
摘要：Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, a j-restricted k-matching is a k-matching with each connected component having at least j + 1 edges, and the total node weight of a j-restricted k-matching is the total weight of the nodes covered by the edges in the j-restricted k-matching. When j = 1 and k = 2, Kaneko [Kaneko A ...
-
作者：Blanchet, Jose; Lam, Henry
作者单位：Columbia University; Columbia University; Boston University
摘要：We develop rare-event simulation methodology for the analysis of loss events in a many-server loss system under the quality-driven regime, focusing on the steady-state loss probability (i.e., fraction of lost customers over arrivals) and the behavior of the whole system leading to loss events. The analysis of these events requires working with the full measure-valued process describing the system. This is the first algorithm that is shown to be asymptotically optimal, in the rare-event simulat...
-
作者：Wang, Mengdi; Bertsekas, Dimitri P.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x(k)} that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditio...
-
作者：Gamarnik, David; Goldberg, David A.; Weber, Theophane
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider a decision network on an undirected graph in which each node corresponds to a decision variable, and each node and edge of the graph is associated with a reward function whose value depends only on the variables of the corresponding nodes. The goal is to construct a decision vector that maximizes the total reward. This decision problem encompasses a variety of models, including maximum-likelihood inference in graphical models (Markov Random Fields), combinatorial optimization on gr...
-
作者：Oksendal, Bernt; Sulem, Agnes; Zhang, Tusheng
作者单位：University of Oslo; Universite Gustave-Eiffel; University of Manchester
摘要：We consider general singular control problems for random fields given by a stochastic partial differential equation (SPDE). We show that under some conditions the optimal singular control can be identified with the solution of a coupled system of SPDE and a reflected backward SPDE (RBSPDE). As an illustration we apply the result to a singular optimal harvesting problem from a population whose density is modeled as a stochastic reaction-diffusion equation. Existence and uniqueness of solutions ...
-
作者：Molinaro, Marco; Ravi, R.
作者单位：Carnegie Mellon University
摘要：We consider packing linear programs with m rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive to obtain a feasible solution maximizing the expected reward. Previous (1 - epsilon)-competitive algorithms require the right-hand side of the linear program to be Omega((m/epsilon(2))log(n/epsilon)), a bound that worsens with the number of column...
-
作者：Eaves, B. Curtis; Rothblum, Uriel G.
作者单位：Stanford University; Technion Israel Institute of Technology
摘要：A linear problem is completely solved by a randomizing linear algorithm if the set of data-solution pairs of the problem equals the set of input-output pairs of the algorithm over all randomizations. Linear problems are based on the predicate language over ordered fields. This class contains, for example, all linear programs, all bounded variable integer programs, all satisfiability problems in sentential logic, and models of conflict. Randomizing linear algorithms are based on a tree, arithme...
-
作者：Jonckheere, Matthieu; Lopez, Sergio
作者单位：Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); University of Buenos Aires; Universidad Nacional Autonoma de Mexico
摘要：We address a conjecture introduced by Massoulie [Massoulie L (2007) Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab. 17(3):809-839], concerning the large deviations of the stationary measure of bandwidth-sharing networks functioning under the proportional fair allocation. For Markovian networks, we prove that proportional fair and an associated reversible allocation are geometrically ergodic and have the same large deviations characteristics using...
-
作者：Buchbinder, Niv; Jain, Kamal; Singh, Mohit
作者单位：Tel Aviv University; eBay Inc.; Microsoft
摘要：In the classical secretary problem an employer would like to choose the best candidate among n competing candidates that arrive in a random order. In each iteration, one candidate's rank vis-a-vis previously arrived candidates is revealed and the employer makes an irrevocable decision about her selection. This basic concept of n elements arriving in a random order and irrevocable decisions made by an algorithm have been explored extensively over the years, and used for modeling the behavior of...
