Geographic Quorum System Approximations

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in the plane (representing servers) into quorums (i.e., clusters) of size k. The distance between a point p and a cluster C is the Euclidean distance between p and the site in C that is the farthest from p. We present a near linear time constant-factor approximation algorithm for partitioning X into clusters, such that the maximal distance between a point in the underlying region and its closest cluster is minimized. Next, we describe a data structure for answering (approximately) nearest-neighbor queries on such a clustering. Finally, we study the problem of partitioning into clusters with an additional load-balancing requirement.     

Metals in Ancient Israel: Archaeological Interperetation of Chemical Analysis

Over a thousand metal finds are now known from Chalcolithic and Early Bronze habitation sites, burial caves, and hoards in Israel and Jordan. To answer the question as to how these artifacts were made, more than 200 objects were sampled for metallographic analysis and for chemical analysis by electron-probe X-ray microanalysis and by atomic absorption spectrophotometry. In the Chalcolithic period (4th millennium BC), within a confined zone of southern Israel and Jordan, three entirely different groups of metal objects were found together. Various materials (Cu-As-Sb; Au; Cu) from totally separate sources were used in diverse production methods to produce specific classes of objects, of a specific shape and color, totally different from one another. In contrast, the components of Early Bronze Age (3rd millennium BC) metal production indicate a fundamental change in the structure and level of craft specialization. This change may be recognized mainly by the unity of the repertory of objects and the use of the same source-metal (Ag; Au; Cu) for a wider range of products, as well as by the total technological and geographical separation between extraction and production. The transformation from proto-urban to urban society documents an important stage of social, economic, and political development in Early Bronze Age Israel and Jordan. Many explanations have been offered for this transformation, most of them based on external intervention or stimulus. This paper adds to the existing arguments for the beginning of urbanization, the missing local socioeconomic factor, based on changes in social complexity as reflected in the first two thousand years of metallurgy.     

How Fast Is the k-Means Method?

We present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. Lloyds method) for k-means clustering. Our upper bounds are polynomial in the number of points, number of clusters, and the spread of the point set. We also present a lower bound, showing that in the worst case the k-means heuristic needs to perform (n) iterations, for n points on the real line and two centers. Surprisingly, the spread of the point set in this construction is polynomial. This is the first construction showing that the k-means heuristic requires more than a polylogarithmic number of iterations. Furthermore, we present two alternative algorithms, with guaranteed performance, which are simple variants of the k-means method. Results of our experimental studies on these algorithms are also presented.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

Near-Linear Time Approximation Algorithms for Curve Simplification

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P’ whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ² in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L_p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.     

Naval Mine Countermeasure Missions

Undersea operations using autonomous underwater vehicles (AUVs) provide a different and in some ways a more challenging problem than tasks for unmanned aerial vehicles and unmanned ground vehicles. In particular, in undersea operations, communication windows are restricted, and bandwidth is limited. Consequently, coordination among agents is correspondingly more difficult. In traditional approaches, a central planner initially assigns subtasks to a set of AUVs to achieve the team goal. However, those initial task assignments may become inefficient during real-time execution because of the real-world issues such as failures. Therefore, initial task allocations are usually subject to change if efficiency is a high concern. Reallocations are needed and should be performed in a distributed manner. To provide such flexibility, we propose a distributed auction-based cooperation framework, distributed and efficient multirobot-cooperation framework (DEMiR-CF), which is an online dynamic task allocation (reallocation) system that aims to achieve a team goal while using resources effectively. DEMiR-CF, with integrated task scheduling and execution capabilities, can also respond to and recover from real-time contingencies such as communication failures, delays, range limitations, and robot failures.     

Fast Algorithms for Computing the Smallest k-Enclosing Circle

For a set $P$ of $n$ points in the plane and an integer $k \leq n$, consider the problem of finding the smallest circle enclosing at least $k$ points of $P$. We present a randomized algorithm that computes in $O( n k )$ expected time such a circle, improving over previously known algorithms. Further, we present a linear time $\delta$-approximation algorithm that outputs a circle that contains at least $k$ points of $P$ and has radius less than $(1+\delta)r_{opt}(P,k)$, where $r_{opt}(P,k)$ is the radius of the minimum circle containing at least $k$ points of $P$. The expected running time of this approximation algorithm is $O(n + n \cdot\min((1/k\delta^3) \log^2 (1/\delta), k))$.