Search

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a “good” hierarchical clustering is one that minimizes a particular cost function [23]. He showed that this cost function has certain desirable properties: To achieve optimal cost, disconnected components (namely, dissimilar elements) must be separated at higher levels of the hierarchy, and when the similarity between data elements is identical, all clusterings achieve the same cost. We take an axiomatic approach to defining “good” objective functions for both similarity- and dissimilarity-based hierarchical clustering. We characterize a set of admissible objective functions having the property that when the input admits a “natural” ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. We show that this set includes the objective function introduced by Dasgupta. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. We also initiate a beyond worst-case analysis of the complexity of the problem and design algorithms for this scenario. [ABSTRACT FROM AUTHOR]

Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as that of Cooper et al., the coalescence time for graphs, such as binary trees, d-dimensional tori, hypercubes, and, more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log² n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst-case bound for the coalescence time of O(n³). By duality, our results yield identical bounds on the voter model. Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill. [ABSTRACT FROM AUTHOR]

In this article, we characterize the advantage of using a robot’s neighborhood to find and eliminate adversarial robots in the presence of a Sybil attack. We show that by leveraging the opinions of their neighbors on the trustworthiness of transmitted data, robots can detect adversaries with high probability. We characterize the number of communication rounds required to be a function of the communication quality and of the proportion of legitimate to malicious robots. This result enables increased resiliency of many multirobot algorithms. Because our results are finite time and not asymptotic, they are particularly well-suited for problems of a time critical nature. We develop two algorithms, FindSpoofedRobots that determines trusted neighbors with high probability, and FindResilientAdjacencyMatrix that enables distributed computation of graph properties in an adversarial setting. We apply our methods to a flocking problem where a team of robots must track a moving target in the presence of adversarial robots. We show that by using our algorithms, the team of robots are able to maintain tracking ability of the dynamic target. [ABSTRACT FROM AUTHOR]

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms that are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of O(d min { &sqrt; log n/μ,&sqrt; n}) in time O(T), where μ is the spectral gap of the transition matrix of the graph. We also show that, in general, neither of these assumptions may be omitted without increasing discrepancy. We then show, by a combinatorial potential reduction argument, that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of O(d) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes. [ABSTRACT FROM AUTHOR]

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m ≥ n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a threshold and we are interested in the balancing time, i.e., the time it takes until the load of all resources is below or at the threshold. We distinguish between resource-based and user-based protocols. In the case of resource-based protocols, resources with a load larger than the threshold are allowed to send tasks to neighboring resources. In the case of user-based protocols, the tasks make the migration decisions and we restrict ourselves to the complete graph in the model. Any task allocated to a resource with a load above the threshold decides whether to migrate to a neighboring resource independently of the other tasks. For resource-controlled protocols, we present results for arbitrary graphs. For the user-controlled migration, we consider complete graphs and derive bounds for both above-average and tight thresholds. [ABSTRACT FROM AUTHOR]