enter search term and/or author name
Clustering for metric and nonmetric distance measures
Marcel R. Ackermann, Johannes Blömer, Christian Sohler
Article No.: 59
We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors...
We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay . The algorithm takes as input a bipartite graph G, a starting vertex v, and a parameter...
A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in...
We study a bichromatic version of the well-known k-set problem: given two sets R and B of points of total size n and an integer k, how many subsets of the form (R∩ h) ∪ (B∖...
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
Kenneth L. Clarkson
Article No.: 63
The problem of maximizing a concave function f(x) in the unit simplex Δ can be solved approximately by a simple greedy algorithm. For given k, the algorithm can find a point x(k) on a...
A near-linear-time algorithm for computing replacement paths in planar directed graphs
Yuval Emek, David Peleg, Liam Roditty
Article No.: 64
Let (G = (V(G),E(G))) be a directed graph with nonnegative edge lengths and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for...
Two-phase greedy algorithms for some classes of combinatorial linear programs
Ulrich Faigle, Britta Peis
Article No.: 65
We present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of Hoffman and Schwartz' lattice polyhedra. Our algorithms compute in a first phase Monge solutions for the associated...
A common approach for dealing with large datasets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive datasets, however, even making a single pass over the data is prohibitive. Therefore,...
Geodesic delaunay triangulations in bounded planar domains
Steve Y. Oudot, Leonidas J. Guibas, Jie Gao, Yue Wang
Article No.: 67
We introduce a new feature size for bounded domains in the plane endowed with an intrinsic metric. Given a point x in a domain X, the systolic feature size of X at x measures half the length of the shortest loop...
We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past...
We study the lower-bounded facility location problem which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this...
Nondecreasing paths in a weighted graph or: How to optimally read a train schedule
Virginia Vassilevska Williams
Article No.: 70
A travel booking office has timetables giving arrival and departure times for all scheduled trains, including their origins and destinations. A customer presents a starting station and demands a route with perhaps several train connections taking...
Hausdorff distance under translation for points and balls
Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Yusu Wang
Article No.: 71
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the article, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that...
Finding equitable convex partitions of points in a polygon efficiently
John Gunnar Carlsson, Benjamin Armbruster, Yinyu Ye
Article No.: 72
Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into n convex pieces each containing an equal number of red and blue points. Motivated by a vehicle routing heuristic, we look at a...