-
作者：Dayanik, Savas
作者单位：Ihsan Dogramaci Bilkent University; Ihsan Dogramaci Bilkent University
摘要：Suppose that a Wiener process gains a known drift rate at some unobservable disorder time with some zero-modified exponential distribution. The process is observed only at known fixed discrete time epochs, which may not always be spaced in equal distances. The problem is to detect the disorder time as quickly as possible by means of an alarm that depends only on the observations of Wiener process at those discrete time epochs. We show that Bayes optimal alarm times, which minimize expected tot...
-
作者：Flesch, Janos; Kuipers, Jeroen; Mashiah-Yaakovi, Ayala; Schoenmakers, Gijs; Solan, Eilon; Vrieze, Koos
作者单位：Maastricht University; Maastricht University; Tel Aviv University
摘要：We prove that every multiplayer perfect-information game with bounded and lower-semicontinuous payoffs admits a subgame-perfect epsilon-equilibrium in pure strategies. This result complements Example 3 in Solan and Vieille [Solan, E., N. Vieille. 2003. Deterministic multi-player Dynkin games. J. Math. Econom. 39 911-929], which shows that a subgame-perfect epsilon-equilibrium in pure strategies need not exist when the payoffs are not lower-semicontinuous. In addition, if the range of payoffs i...
-
作者：Subramanian, Vijay G.
作者单位：Maynooth University
摘要：We consider a single server discrete-time system with a fixed number of users where the server picks operating points from a compact, convex, and coordinate convex set. For this system, we analyse the performance of a stabilising policy that at any given time picks operating points from the allowed rate region that maximise a weighted sum of rates, where the weights depend on the work loads of the users. Assuming a large deviations principle (LDP) for the arrival processes in the Skorohod spac...
-
作者：Jelenkovic, Predrag R.; Tan, Jian
作者单位：Columbia University; International Business Machines (IBM); IBM USA
摘要：Power law distributions have been repeatedly observed in a wide variety of socioeconomic, biological, and technological areas. In many of the observations, e. g., city populations and sizes of living organisms, the objects of interest evolve because of the replication of their many independent components, e. g., births and deaths of individuals and replications of cells. Furthermore, the rates of replications are often controlled by exogenous parameters causing periods of expansion and contrac...
-
作者：Lee, Jon; Sviridenko, Maxim; Vondrak, Jan
作者单位：International Business Machines (IBM); IBM USA; International Business Machines (IBM); IBM USA
摘要：Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k >= 2 and any epsilon > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular ...
-
作者：Zheng, Xiaojin; Sun, Xiaoling; Li, Duan; Xia, Yong
作者单位：Fudan University; Chinese University of Hong Kong; Beihang University
摘要：We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the...
