11191590
On parallel integer sorting
We present an optimal algorithm for sortingn integers in the range [1,nc] (for any constantc) for the EREW PRAM model where the word length isnε, for any ε>0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.
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.
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).
6305829
Online Smoothing of Variable-Bit-Rate Streaming Video
Bandwidth smoothing techniques for stored video perform end to end workahead transmission of frames into the client playback buffer, in advance of their display times. Such techniques are very effective in reducing the burstiness of the bandwidth requirements for transmitting compressed, stored video. This paper addresses online bandwidth smoothing for a growing number of streaming video applications such as newscasts, sportscasts, and distance learning, where many clients may be willing to tolerate a playback delay of a few seconds in exchange for a smaller bandwidth requirement. The smoothing can be performed at either the source of the videocast or at special smoothing server(s) (e.g., proxies or gateways) within the network. In contrast to previous work on stored video, the online smoothing server has limited knowledge of frame sizes and access to only a segment of the video at a time. This is either because the feed is live or because it is streaming past the server. We formulate an online smoothing model which incorporates playback delay, client and server buffer sizes, server processing capacity, and frame size prediction techniques. Our model can accommodate an arbitrary arrival process. Using techniques for smoothing stored video at the source as a starting point, we develop an online, window-based smoothing algorithm for delay tolerant applications. Extensive experiments with MPEG-1 and M-JPEG video traces demonstrate that online smoothing significantly reduces the peak rate, coefficient of variation, and effective bandwidth of variable-bit-rate video streams. These reductions can be achieved with modest playback delays of a few seconds to a few tens of seconds and moderate client buffer sizes, and closely approximate the performance of optimal offline smoothing of stored video. In addition, we show that frame size prediction can offer further reduction in resource requirements, though prediction becomes relatively less important for longer playback delays. However, the ability to predict future frame sizes affects the appropriate division of buffer space between the server and client sites. Our experiments show that the optimal buffer allocation shifts to placing more memory at the server as the server has progressively less information about future frame sizes.
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.
5956748
Evaluating bidding strategies for simultaneous auctions
Bidding for multiple items or bundles on online auctions raises challenging problems. We assume that an agent has a valuation function that returns its valuation for an arbitrary bundle. In the real world all or most of the items of interest to an agent is not present in a single combinatorial auction. We study the problem of bidding for multiple items in a set of simultaneous auctions, each of which sell only a single unit of a particular item. Hence an agent has to bid in multiple auctions to obtain preferred item bundles. While an optimal bidding strategy is known when bidding in sequential auctions, only suboptimal strategies are available when bidding for items sold in auctions running simultaneously. To decide on an agent's bid for simultaneous auctions, we investigate a multi-dimensional bid improvement strategy, which is optimal given an infinite number of restarts. We provide a comparison of this algorithm with existing ones, both in terms of utilities generated and computation time, along with a discussion of the strengths and weaknesses of these strategies.
9417710
Using real-valued genetic algorithms to evolve rule sets for classification
In this paper, we use a genetic algorithm to evolve a set of classification rules with real-valued attributes. We show how real-valued attribute ranges could be encoded with real-valued genes and present a new uniform method for representing don't cares in the rules. We view supervised classification as an optimization problem, and evolve rule sets that maximize the number of correct classifications of input instances. We use a variant of the Pitt approach to genetic-based machine learning system with a novel conflict resolution mechanism between competing rules within the same rule set. Experimental results demonstrate the effectiveness of our proposed approach on a benchmark wine classifier system.<<ETX>>
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.