Search

The sets of hyperlinks in web pages, relationship ties in social networks, or sets of recommendations in recommender systems, have a major impact on the diversity of content accessed by the user in a browsing session. Bias induced by the graph structure may trap a reader in a polarized bubble with no access to other opinions. It is widely accepted that exposure to diverse opinions creates more informed citizens and consumers. We introduce the concept of the polarized bubble radius of a node, as the expected length of a random walk from it to a node of different opinion. Using the bubble radius, we define the measures of structural bias and diverse navigability to quantify the effect of links and recommendations on the diversity of content visited in a browsing session. We then propose algorithmic techniques to reduce the structural bias of the graph or improve the diverse navigability of the system through minimal modifications, such as edge insertions or flipping the order of existing links or recommendations, corresponding to switching the edge traversal probabilities. Under mild conditions, our techniques obtain a constant factor-approximation of their respective tasks. In our extensive experimental evaluation, we show that our algorithms reduce the structural bias or improve the diverse navigability faster than appropriate baselines, including some designed with the goal of reducing the polarization of a graph. [ABSTRACT FROM AUTHOR]

We study the use of sampling for efficiently mining the top- K frequent itemsets of cardinality at most w. To this purpose, we define an approximation to the top- K frequent itemsets to be a family of itemsets which includes (resp., excludes) all very frequent (resp., very infrequent) itemsets, together with an estimate of these itemsets’ frequencies with a bounded error. Our first result is an upper bound on the sample size which guarantees that the top- K frequent itemsets mined from a random sample of that size approximate the actual top- K frequent itemsets, with probability larger than a specified value. We show that the upper bound is asymptotically tight when w is constant. Our main algorithmic contribution is a progressive sampling approach, combined with suitable stopping conditions, which on appropriate inputs is able to extract approximate top- K frequent itemsets from samples whose sizes are smaller than the general upper bound. In order to test the stopping conditions, this approach maintains the frequency of all itemsets encountered, which is practical only for small w. However, we show how this problem can be mitigated by using a variation of Bloom filters. A number of experiments conducted on both synthetic and real benchmark datasets show that using samples substantially smaller than the original dataset (i.e., of size defined by the upper bound or reached through the progressive sampling approach) enable to approximate the actual top- K frequent itemsets with accuracy much higher than what analytically proved. [ABSTRACT FROM AUTHOR]

This paper considers online stochastic combinatorial optimization problems where uncertainties, i.e., which requests come and when, are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes online stochastic algorithms that combine the frameworks of online and stochastic optimization. Online stochastic algorithms differ from traditional a priori methods such as stochastic programming and Markov Decision Processes by focusing on the instance data that is revealed over time. The paper proposes three main algorithms: expectation E, consensus C, and regret R. They all make online decisions by approximating, for each decision, the solution to a multi-stage stochastic program using an exterior sampling method and a polynomial number of samples. The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that, under assumptions which seem to hold on these, and other, applications, algorithm E has an expected constant loss compared to the offline optimal solution. Algorithm R reduces the number of optimizations by a factor | R|, where R is the number of requests, and has an expected ρ(1+ o(1)) loss when the regret gives a ρ-approximation to the offline problem. [ABSTRACT FROM AUTHOR]

We consider a random sequence of calls between nodes in a complete network with link capacities. Each call first tries the direct link. If that link is saturated, then the `first-fit dynamic alternative routing algorithm' sequentially selects up to d random two-link alternative routes, and assigns the call to the first route with spare capacity on each link, if there is such a route. The `balanced dynamic alternative routing algorithm' simultaneously selects d random two-link alternative routes; and the call is accepted on a route minimising the maximum of the loads on its two links, provided neither of these two links is saturated. We determine the capacities needed for these algorithms to route calls successfully, and find that the second `balanced' algorithm requires a much smaller capacity. Our results strengthen and extend the discrete-time results presented in [10]. [ABSTRACT FROM AUTHOR]