1922221
Improved Algorithms for Uniform Partitions of Points

AbstractWe consider the following one- and two-dimensional bucketing problems: Given a set S of n points in \reals1 or \reals2 and a positive integer b , distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lie in each bucket in an optimal solution. We present algorithms whose time complexities depend on b and Δ . No prior knowledge of Δ is necessary for our algorithms.For the one-dimensional problem, we give a deterministic algorithm that achieves a running time of O(b4 (Δ2+log n) + n) . For the two-dimensional problem, we present a Monte Carlo algorithm that runs in subquadratic time for small values of b and Δ . The previous algorithms, by Asano and Tokuyama [1], searched the entire parameterized space and required Ω ( n2 ) time in the worst case even for constant values of b and Δ . We also present a subquadratic algorithm for the special case of the two-dimensional problem when b=2 .

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.
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).
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.
5997994
Evolving Cooperation Strategies
We propose an approach to developing cooperation strategies for multiagent problem solving situations which is different from existing techniques in two ways: strategies are incrementally constructed by repeatedly solving problems in the domain, i.e., on-line; and, we utilize an automated method of strategy formulation and modification, that relies little on domain details and human expertise, and more on performance on randomly generated problems in the domain. The genetic programming (GP) (Koza 1992) paradigm used to develop, through repeated problem solving, increasingly efficient strategies. Populations of structures are represented as Lisp symbolic expressions (Sexpressions). These are manipulated to evolve better structures by propagating and combining parts of structures that perform well compared to others in the population. To use this approach, we have to develop an encoding of strategies as S-expressions and choose an evaluation criterion for a strategy corresponding to an arbitrary S-expression. Strategies are evaluated by allowing the agents to execute them in the application domain and by measuring their efficiency and effectiveness by a set of criteria relevant to the domain.
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.
6541963
Fast convergence to satisfying distributions
We investigate an environment where self-interested agents have to find high-quality service resources. Agents have common knowledge about resources which are able to provide these services. The performance of resources is measured by the satisfaction obtained by agents using them. The performance of a resource depends on its intrinsic capability and its current load. We use a satisfying rather than an optimizing framework, where agents are content to receive service quality above a threshold. We introduce a formal framework to characterize the convergence of agents to a state where each agent is satisfied with the performance of the service it is currently using. We analyzed the convergence behavior of such a system and identified a mechanism to speed up convergence.
2290480
Optimal multicast smoothing of streaming video over an internetwork
A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. We propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, the optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.
13052705
Learning to Coordinate without Sharing Information
Researchers in the field of Distributed Artificial Intelligence (DAI) have been developing efficient mechanisms to coordinate the activities of multiple autonomous agents. The need for coordination arises because agents have to share resources and expertise required to achieve their goals. Previous work in the area includes using sophisticated information exchange protocols, investigating heuristics for negotiation, and developing formal models of possibilities of conflict and cooperation among agent interests. In order to handle the changing requirements of continuous and dynamic environments, we propose learning as a means to provide additional possibilities for effective coordination. We use reinforcement learning techniques on a block pushing problem to show that agents can learn complimentary policies to follow a desired path without any knowledge about each other. We theoretically analyze and experimentally verify the effects of learning rate on system convergence, and demonstrate benefits of using learned coordination knowledge on similar problems. Reinforcement learning based coordination can be achieved in both cooperative and non-cooperative domains, and in domains with noisy communication channels and other stochastic characteristics that present a formidable challenge to using other coordination schemes.