Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where is upper bounded by the largest value observed by any node.
Following the idea of studying competitive algorithms for monitoring streams and the notion of filters, @cite_1 present an algorithm for online dominance tracking of distributed streams. In this problem a coordinator always has to be informed about the dominance relationship between @math distributed nodes each observing an online stream of @math -dimensional values. Here, the dominance relation of two nodes @math and @math currently observing @math and @math , respectively, both from @math , is defined as @math dominates @math if @math for some @math and @math for all other @math . Their algorithm is based on the idea of assigning filters to the nodes and they show that a mid-point strategy, which basically sets filters to be the mid-point between neighboring nodes, is @math -competitive with respect to the number of messages sent in comparison to an offline algorithm that sets filters optimally.
@cite_1
1604641903
In this paper, we study the dominance relation under a stochastic setting. Let @math be a set of @math colored stochastic points in @math , each of which is associated with an existence probability. We investigate the problem of computing the probability that a realization of @math contains inter-color dominances, which we call the (CSD) problem. We propose the first algorithm to solve the CSD problem for @math in @math time. On the other hand, we prove that, for @math , even the CSD problem with a restricted color pattern is #P-hard. In addition, even if the existence probabilities are restricted to be @math , the problem remains #P-hard for @math . A simple FPRAS is then provided to approximate the desired probability in any dimension. We also study a variant of the CSD problem in which the dominance relation is considered with respect to not only the standard basis but any orthogonal basis of @math . Specifically, this variant, which we call the free-basis colored stochastic dominance (FBCSD) problem, considers the probability that a realization of @math contains inter-color dominances with respect to any orthogonal basis of @math . We show that the CSD problem is polynomial-time reducible to the FBCSD problem in the same dimension, which proves the #P-hardness of the latter for @math . Conversely, we reduce the FBCSD problem in @math to the CSD problem in @math , by which an @math time algorithm for the former is obtained. Influence problem is one of the central problems in the study of online social networks, the goal of which is to influence all nodes with the minimum number of seeds. However, in the real world, it might be too expensive to influence all nodes. In many cases, it is satisfactory to influence nodes only up to some percent p. In this paper, we study the minimum partial positive influence dominating set (MPPIDS) problem. In fact, we presented an approximation algorithm for a more general problem called minimum partial set multicover problem. As a consequence, the MPPIDS problem admits an approximation with performance ratio @math źH(Δ), where @math H(·) is the Harmonic number, @math ź=1 (1-(1-p)ź),źźΔ2 ź, and @math Δ,ź are the maximum degree and the minimum degree of the graph, respectively. For power-law graphs, we show that our algorithm has a constant performance ratio. Let @math , @math for @math , @math bounding the bit length of the coefficients of the @math 's, and let @math be a quantifier-free @math -formula defining a convex semialgebraic set. We design an algorithm returning a rational point in @math if and only if @math . It requires @math bit operations. If a rational point is outputted, its coordinates have bit length dominated by @math . Using this result, we obtain a procedure for deciding whether a polynomial @math is a sum of squares of polynomials in @math . Denote by @math the degree of @math , @math the maximum bit length of the coefficients in @math , @math , and @math . This procedure requires @math bit operations, and the coefficients of the outputted polynomials have bit length dominated by @math . A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, @math the minimum degree, and @math the maximum degree. We show that every graph has a domatic partition with @math dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a @math -approximation algorithm for domatic number, since the domatic number is always at most @math . We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every @math , a @math -approximation implies that @math . This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with @math dominating sets, where the "o(1)" term goes to zero as @math increases. This can be turned into an efficient algorithm that produces a domatic partition of @math sets. A set @math is weakly convex in @math if for any two vertices @math there exists an @math --geodesic such that all of its vertices belong to @math . A set @math is a weakly convex dominating set if @math is weakly convex and dominating. The weakly convex domination number @math of a graph @math equals the minimum cardinality of a weakly convex dominating set in @math . The weakly convex domination subdivision number sd @math is the minimum number of edges that must be subdivided (each edge in @math can be subdivided at most once) in order to increase the weakly convex domination number. In this paper we initiate the study of weakly convex domination subdivision number and we establish upper bounds for it. In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the @math function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve @math distribution-dependent regret and @math distribution-independent regret, where @math is the time horizon. We apply our results to the @math -MAX problem and expected utility maximization problems. In particular, for @math -MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first @math bound on the @math -approximation regret of its online problem, for any @math . This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within @math steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most @math , where @math is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and @math is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion @math , and for any value @math , there exists an initial distribution of tokens with imbalance @math for which the time to reduce the imbalance to even @math is at least @math . The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains @math . Furthermore, we show that upon reaching a state with a global imbalance of @math , the time for this algorithm to locally balance the network can be as large as @math . We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step. We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even though we have them only for some values of @math that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. Given data stream @math of size @math of numbers from @math , the frequency of @math is defined as @math . The @math -th of @math is defined as @math . We consider the problem of approximating frequency moments in insertion-only streams for @math . For any constant @math we show an @math upper bound on the space complexity of the problem. Here @math is the iterative @math function. To simplify the presentation, we make the following assumptions: @math and @math are polynomially far; approximation error @math and parameter @math are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a ; it samples a heavy element (i.e., element @math with frequency @math ) with probability @math and gives approximation @math . In addition, the estimations never exceed the real values, that is @math for all @math . As a result, we reduce the space complexity of finding a heavy element to @math bits. We apply our method of recursive sketches and resolve the problem with @math bits. Let @math be a ground set of @math elements, and let @math be a family of subsets of @math , @math , with a positive cost @math associated with each @math . Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from @math one by one. Once a new element is given, the algorithm has to cover it by some set of @math containing it. We assume that the elements of @math and the members of @math are known in advance to the algorithm; however, the set @math of elements given by the adversary is not known in advance to the algorithm. (In general, @math may be a strict subset of @math .) The objective is to minimize the total cost of the sets chosen by the algorithm. Let @math denote the family of sets in @math that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets @math that covers @math . The performance of the algorithm is the ratio between the cost of @math and the cost of @math . The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an @math competitive deterministic algorithm for the problem and establish a nearly matching @math lower bound for all interesting values of @math and @math . The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm. In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of existence and a positive profit, and each node is assigned a positive integer called timeout. We know whether an edge exists or not only after probing it. On this random graph we are executing a process, which one-by-one probes the edges and gradually constructs a matching. The process is constrained in two ways: once an edge is taken it cannot be removed from the matching, and the timeout of node @math upper-bounds the number of edges incident to @math that can be probed. The goal is to maximize the expected profit of the constructed matching. For this problem (Algorithmica 2012) provided a @math -approximation algorithm for bipartite graphs, and a @math -approximation for general graphs. In this work we improve the approximation factors to @math and @math , respectively. We also consider an online version of the bipartite case, where one side of the partition arrives node by node, and each time a node @math arrives we have to decide which edges incident to @math we want to probe, and in which order. Here we present a @math -approximation, improving on the @math -approximation of The main technical ingredient in our result is a novel way of probing edges according to a random but non-uniform permutation. Patching this method with an algorithm that works best for large probability edges (plus some additional ideas) leads to our improved approximation factors. For a pattern graph @math on @math nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of @math in a given large graph @math on @math nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an @math with an independent set of size @math can be computed exactly in @math time and @math space, or in @math time and @math space. (The @math notation omits @math factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a @math matrix over rings and semirings. 2. The number of copies of any @math having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in @math time, where @math is the matrix multiplication exponent and @math is divisible by @math . Similar results hold for other values of @math . Also, the number... We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given @math users, @math movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user @math and movie @math have features @math and @math respectively, and their corresponding rating @math is a noisy measurement of @math for some unknown function @math . In contrast with classical regression, the features @math are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least @math with @math , we prove that the expected fraction of our estimates with error greater than @math is less than @math plus a polynomially decaying term, where @math is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods. We present an algorithm for computing @math , the @math th moment of an @math -dimensional frequency vector of a data stream, for @math , to within @math factors, @math with high constant probability. Let @math be the number of stream records and @math be the largest magnitude of a stream update. The algorithm uses space in bits @math where, @math . Here @math is @math for @math and @math for @math . This improves upon the space required by current algorithms iw:stoc05,bgks:soda06,ako:arxiv10,bo:arxiv10 by a factor of at least @math . The update time is @math . We use a new technique for designing estimators for functions of the form @math , where, @math is a random variable and @math is a smooth function, based on a low-degree Taylor polynomial expansion of @math around an estimate of @math . Motivated by the need to understand the algorithmic foundations of distributed large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where @math machines jointly perform computations on graphs with @math nodes (typically, @math ). The input graph is assumed to be initially randomly partitioned among the @math machines. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. We present (almost) tight bounds for the round complexity of two fundamental graph problems, namely PageRank computation and triangle enumeration. Our tight lower bounds, a main contribution of the paper, are established through an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines for correctly solving a problem. Our approach is generic and might be useful in showing lower bounds in the context of similar problems and similar models. We show a lower bound of @math rounds for computing the PageRank. (Notation @math hides a @math factor.) We also present a simple distributed algorithm that computes the PageRank of all the nodes of a graph in @math rounds (notation @math hides a @math factor and an additive @math term). For triangle enumeration, we show a lower bound of @math rounds, where @math is the number of edges of the graph. Our result implies a lower bound of @math for the congested clique, which is tight up to logarithmic factors. We also present a distributed algorithm that enumerates all the triangles of a graph in @math rounds. The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed @math -coloring algorithm running on the Congested Clique which has an expected running time of (i) @math rounds, if @math ; and (ii) @math rounds otherwise. Applying the simulation theorem to the Congested-Clique @math -coloring algorithm yields an @math -round @math -coloring algorithm in the MapReduce model. Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the @math model), the major impediment to constructing fast algorithms is the @math restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models. We consider the problem of route discovery in a mesh network with faulty nodes. The number and the positions of the faulty nodes are unknown. It is known that a flooding strategy like expanding ring search can route a message linear in the minimum number of steps d while it causes a traffic (i.e. the total number of messages) of @math . For optimizing traffic a single-path strategy is optimal producing traffic @math , where p is the number of nodes that are adjacent to faulty nodes. We present a deterministic multi-path online routing algorithm that delivers a message within @math time steps causing traffic @math . This algorithm is asymptotically as fast as flooding and nearly traffic-optimal up to a polylogarithmic factor. We present the communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of , a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1 @math (T ) @math T @math O( n) @math (T ) @math O( n) @math ( n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs. This paper studies the basic question of whether a given channel @math can be dominated (in the precise sense of being more noisy) by a @math -ary symmetric channel. The concept of "less noisy" relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence. We provide an equivalent characterization in terms of @math -divergence. Furthermore, we develop a simple criterion for domination by a @math -ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel @math . The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel. Stochastic Gradient Langevin Dynamics (SGLD) is a combination of a Robbins-Monro type algorithm with Langevin dynamics. In this paper, the SGLD method with fixed step size @math is considered in order to sample from a logconcave target distribution @math , known up to a normalisation factor. We assume that unbiased estimates of the gradient from possibly dependent observations are available. It is shown that, for all @math , the Wasserstein- @math distance of the @math th iterate of the SGLD algorithm from @math is dominated by @math with appropriate constants @math and @math , whereas for the case of i.i.d. data the upper bound is improved to @math .