33712953
Fractional Cascading Simplified
We give an alternate implementation of the fractional cascading data-structure of Chazelle and Guibas to do iterative search for a key in multiple ordered lists. The construction of our data-structure uses randomization and simplifies the algorithm of Chazelle and Guibas vastly making it practical to implement. Although our bounds are asymptotically similar to the earlier ones, there are improvements in the constant factors. Our analysis is novel and captures some of the inherent difficulties associated with the fractional casading data structure. In particular, we use tools from branching process theory and derive some useful asymptotic bounds. The probability of deviation from the expected performance bounds decreases rapidly with number of keys.
10562059
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O(1) query time, require O(\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O(n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O(n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O(n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O(\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O(1) time. This improves the previous best known update bound by a factor of log n. For maintaining all-pairs shortest paths, we present an algorithm that achieves O(\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O(\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0, that achieves a sub-quadratic update time of O(n log2n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O(1/nc) for any constant c).
11169442
Linear Time Algorithms for Clustering Problems in Any Dimensions
We generalize the k-means algorithm presented by the authors [14] and show that the resulting algorithm can solve a larger class of clustering problems that satisfy certain properties (existence of a random sampling procedure and tightness). We prove these properties for the k-median and the discrete k-means clustering problems, resulting in O(2(k/e)O(1)dn) time (1+e)-approximation algorithms for these problems. These are the first algorithms for these problems linear in the size of the input (nd for n points in d dimensions), independent of dimensions in the exponent, assuming k and e to be fixed. A key ingredient of the k-median result is a (1+e)-approximation algorithm for the 1-median problem which has running time O(2(1/e)O(1)d). The previous best known algorithm for this problem had linear running time.
9302549
Planar Graph Blocking for External Searching

AbstractWe present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.

32334601
Finding an Approximate Median with High Probability in Constant Parallel Time
Given n elements from a totally ordered set we outline a method for choosing an element whose rank is γn for some 0 0.
1068367
An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains
Abstract. We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log 4 n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms.
5984823
The evolution and stability of cooperative traits
Recent works in multi-agent systems have identified agent behaviors that can develop and sustain mutually beneficial cooperative relationships with like-minded agents and can resist exploitation from selfish agents. Researchers have proposed the use of a probabilistic reciprocity scheme that uses summary information from past interactions to decide whether or not to honor a request for help from another agent. This behavior has been found to be close to optimal in homogeneous groups and outperform exploiters in mixed groups. A major shortcoming of these experiments, however, is that the composition of the group in term of agent behaviors is fixed. We believe that real-life rational agents, on the contrary, will change their behaviors based on observed performances of different behavioral traits with the goal of maximizing performance. In this paper, we present results from experiments on two distinct domains with population groups whose behavioral composition changes based on the performance of the agents. Based on the experimental results, we identify ecological niches for variants of exploitative selfish agents and robust reciprocative agents.
16541041
Helping based on future expectations
Autonomous agents interacting in an open world can be considered to be primarily driven by self interests. Previous work in this area has prescribed a strategy of reciprocal behavior, based on past interactions, for promoting and sustaining cooperation among such self-interested agents. Here we present a new mechanism where agents base their decisions both on historical data as well as on future interaction expectations. A decision mechanism is presented that compares current helping cost with expected future savings from interaction with the agent requesting help. We experiment with heterogeneous agents that have varying expertise for different job types. We evaluate the effect of both change of agent expertise and distribution of task types on subsequent agent relationships. The reciprocity mechanism based on future expectations is found to be robust and flexible in adjusting to the environmental dynamics.
207161230
FeedMe: a collaborative alert filtering system
As the number of alerts generated by collaborative applications grows, users receive more unwanted alerts. FeedMe is a general alert management system based on XML feed protocols such as RSS and ATOM. In addition to traditional rule-based alert filtering, FeedMe uses techniques from machine-learning to infer alert preferences based on user feedback. In this paper, we present and evaluate a new collaborative naïve Bayes filtering algorithm. Using FeedMe, we collected alert ratings from 33 users over 29 days. We used the data to design and verify the accuracy of the filtering algorithm and provide insights into alert prediction.
16079000
Searching for optimal coalition structures
Coalition formation has been a very active area of research in multiagent systems. Most of this research has concentrated on decentralized procedures that allow self-interested agents to negotiate the formation of coalitions and division of coalition payoffs. A different line of research has addressed the problem of finding the optimal division of agents into coalitions such that the sum total of the the payoffs to all the coalitions is maximized (Larson and Sandholm, 1999). This is the optimal coalition structure identification problem. Deterministic search algorithms have been proposed and evaluated under the assumption that the performance of a coalition is independent of other coalitions. We use an order-based genetic algorithm (OBGA) as a stochastic search process to identify the optimal coalition structure. We compare the performance of the OBGA with a representative deterministic algorithm presented in the literature. Though the OBGA has no performance guarantees, it is found to dominate the deterministic algorithm in a significant number of problem settings. An additional advantage of the OBGA is its scalability to larger problem sizes and to problems where performance of a coalition depends on other coalitions in the environment.
15974834
Learning Pareto-optimal Solutions in 2x2 Conflict Games
Multiagent learning literature has investigated iterated two-player games to develop mechanisms that allow agents to learn to converge on Nash Equilibrium strategy profiles. Such equilibrium configurations imply that no player has the motivation to unilaterally change its strategy. Often, in general sum games, a higher payoff can be obtained by both players if one chooses not to respond myopically to the other player. By developing mutual trust, agents can avoid immediate best responses that will lead to a Nash Equilibrium with lesser payoff. In this paper we experiment with agents who select actions based on expected utility calculations that incorporate the observed frequencies of the actions of the opponent(s). We augment these stochastically greedy agents with an interesting action revelation strategy that involves strategic declaration of one's commitment to an action to avoid worst-case, pessimistic moves. We argue that in certain situations, such apparently risky action revelation can indeed produce better payoffs than a non-revealing approach. In particular, it is possible to obtain Pareto-optimal Nash Equilibrium outcomes. We improve on the outcome efficiency of a previous algorithm and present results over the set of structurally distinct two-person two-action conflict games where the players' preferences form a total order over the possible outcomes. We also present results on a large number of randomly generated payoff matrices of varying sizes and compare the payoffs of strategically revealing learners to payoffs at Nash equilibrium.