42428189
Lower Bounds for Parallel Algebraic Decision Trees, Complexity of Convex Hulls and Related Problems
We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W ⊑ R n using p processors, requires Ω(¦W¦/n log(p/n)) rounds where ¦W¦ is the number of connected components of W. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds.
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.
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).
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.

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.
16723670
PLEASE: A Prototype Learning System Using Genetic Algorithms
Prototypes have been proposed as representation of concepts that are used eeec-tively by humans. Developing computational schemes for generating prototypes from examples , however, has proved to be a dii-cult problem. We present a novel genetic algorithm based prototype learning system, PLEASE, for constructing appropriate prototypes from classiied training instances. After constructing a set of prototypes for each of the possible classes, the class of a new input instance is determined by the nearest prototype to this instance. Attributes are assumed to be ordinal in nature and prototypes are represented as sets of feature-value pairs. A genetic algorithm is used to evolve the number of prototypes per class and their positions on the input space. We present experimental results on a series of artiicial problems of varying complexity. PLEASE performs competitively with several nearest neighbor clas-siication algorithms on the problem set. An analysis of the strengths and weaknesses of the initial version of our system motivates the need for additional operators. The inclusion of these operators substantially improves the performance of the system on particularly diicult problems.
2669772
Effect of deceptive referrals on system stability
We study the problem of agents attempting to find quality service providers in a distributed environment. While referrals from other agents can be used to locate high-quality providers, referrers may be malicious and provide incorrect referrals to reduce traffic to their preferred service providers. Whereas apparently it would seem that such deceptive referrals can disrupt system stability, we observe that homogeneous groups of deceptive referrals converge faster to stable agent distributions over service providers compared to homogeneous groups of truthful referrers. We conjecture that deceptive referrers can unwittingly reduce the entropy, a measure of volatility, of the system as the recipient of a bad referral may not be inclined to move even if it is not satisfied with its current service providers. Additionally, we observe that mixed groups of truthful and deceptive referrers converge faster to stable distributions compared to homogeneous group of truthful referrers. These results highlight the unexpected positive effect of deceptive agents in stabilizing a population.
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.
15537048
Modeling opponent decision in repeated one-shot negotiations
In many negotiation and bargaining scenarios, a particular agent may need to interact repeatedly with another agent. Typically, these interactions take place under incomplete information, i.e., an agent does not know exactly which offers may be acceptable to its opponent or what other outside options are available to that other agent. In such situations, an agent can benefit by learning its opponent's decision model based on its past experience. In particular, being able to accurately predict opponent decisions can enable an agent to generate offers to optimize its own utility. In this paper, we present a learning mechanism using Chebychev's polynomials by which an agent can approximately model the decision function used by the other agent based on the decision history of its opponent. We study a repeated one-shot negotiation model which incorporates uncertainty about opponent's valuation and outside options. We evaluate the proposed modeling mechanism for optimizing agent utility when negotiating with different class of opponents.
26714
Local Decision Procedures for Avoiding the Tragedy of Commons
The social sciences literature abound in problems of providing and maintaining a public good in a society composed of self-interested individuals [6]. Public goods are social benefits that can be accessed by individuals irrespective of their personal contributions. Such problems are also addressed in the domain of agent based systems [15]. In this paper we address the problem of the Tragedy of the Commons [9], a particularly common social dilemma that leads to inefficient usage of shared resources. We present a decision procedure following which rational agents can optimally use a shared resource using only local information. Our experimental results confirm that the tragedy of the commons is successfully avoided and the shared resource is utilized to its capacity when agents following our prescribed decision procedure.