7431315
Optimal, Output-sensitive Algorithms for Constructing Planar Hulls in Parallel
Abstract In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(nlogH) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe a very simple O(lognlogH) time optimal deterministic algorithm for the planar hulls which is an improvement over the previously known Ω( log 2 n) time algorithm for small outputs. For larger values of H, we can achieve a running time of O(lognloglogn) steps with optimal work. We also present a fast randomized algorithm that runs in expected time O(logH·loglogn) and does optimal O(nlogH) work. For log H = Ω( loglog n) , we can achieve the optimal running time of O(logH) while simultaneously keeping the work optimal. When logH is o(logn), our results improve upon the previously best known Θ(logn) expected time randomized algorithm of Ghouse and Goodrich. The randomized algorithms do not assume any input distribution and the running times hold with high probability.
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.

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).
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.
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.
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.
482217
Believing others: pro and cons
Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly Sen (1996) has previously presented a prescriptive strategy for promoting and sustaining cooperation among self-interested agents. The adaptive, probabilistic policy prescribed promotes reciprocative cooperation that improves both individual and group performance in the long run. In the short run, however, selfish agents could still exploit reciprocative agents. In this paper we evaluate the hypothesis that the exploitative tendencies of selfish agents can be effectively curbed if reciprocative agents share their "opinions" of other agents. Since the true nature of agents are not known a priori and is learned from experience, believing others can also pose other hazards. We provide a learned trust-based evaluation function that is shown to resist both individual and concerted deception on the part of selfish agents.
2206839
Multi-Dimensional Bid Improvement Algorithm for Simultaneous Auctions
Bidding for multi-items in simultaneous auctions raises challenging problems. In multi-auction settings, the determination of optimal bids by potential buyers requires combinatorial calculations. While an optimal bidding strategy is known when bidding in sequential auctions, only suboptimal strategies are available when bidding for items being sold in simultaneous auctions. We investigate a multi-dimensional bid improvement scheme, motivated by optimization techniques, to derive optimal bids for item bundles in simultaneous auctions. Given a vector of initial bids, the proposed scheme systematically improves bids for each item. Such multi-dimensional improvements result in locally optimal bid vectors. Globally optimal bid vectors are guaranteed in the limit for infinite restarts. For ease of presentation we use two-item scenarios to explain the working of the algorithm. Experimental results show polynomial complexity of variants of this algorithm under different types of bidder valuations for item bundles.
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.
12476704
Strategic bidding for multiple units in simultaneous and sequential auctions
A buyer may be interested in buying a bundle of items, where any one item in the bundle may not be of particular interest. The emergence of online auctions allows such users to obtain bundles by bidding on different simultaneous or sequentially run auctions. Because the number of auctions and the number of combinations to form the bundles may be large, the bundle bidding problem becomes intractable and the user is likely to make suboptimal decision given time constraints and information overload. We believe that an automated agent that can take user preferences and budgetary constraints and can strategically bid on behalf of a user can significantly enhance user profit and satisfaction. Our first step to build such an agent is to consider bundles containing many units of a single a item and auctions that sell only multiple units of one item type. We assume that users obtain goods over several days. Expectations of auctions and their outcome in the future allow the agent to bid strategically on currently open auctions. The agent decides how many items to bid for in the current auctions, and the maximum price to bid for each item. We evaluate our proposed strategy in different configurations: number of items sold, number of auctions opened, expected closing prices, etc. The agent produces greater returns in situations where future auctions can provide better profit, and where not too many agents use our proposed strategy.