[Lowerbounds, Upperbounds]

September 11, 2007

Benoît Hudson
10:00 AM, 3305 Newell-Simon Hall

Thesis Oral

Title: Dynamic Mesh Refinement
Abstract:

Mesh refinement is the problem to produce a triangulation (typically Delaunay) of an input set of points augmented by Steiner points, such that every triangle has good quality (no small angles). The requirement arises from the applications: in scientific computing and in graphics, meshes are often used to discretely represent the value of a function over space. In addition to the quality requirement, the user often has input segments or polygons (generally, a piecewise linear complex) they would like see retained in the mesh; the mesh must respect these constraints. Finally, the mesh should be size-conforming: the size of mesh elements should be related to a particular sizing function based on the distance between input features — in particular, elements should not be too small.

The static meshing problem is increasingly well-understood: one can download software with provable guarantees that on reasonable input, the meshes will have good quality, will respect the input, and will be size-conforming; more recently, these algorithms have started to come with optimal runtimes of O(n log(L/s) + m). As a first result, I present experimental results of the first time-optimal code.

Increasingly, static meshing is insufficient: users want to modify the mesh over time. Throwing away the old mesh and remeshing from scratch is a common approach, but that suffers from slow runtime, and from reinterpolation error because the old and new meshes may be almost unrelated. Mesh stability analyses the correspondence between meshes for two inputs. The main theoretical result of this thesis is an algorithm that has provable bounds on stability: upon inserting or removing a feature that in the final mesh is represented using k points, the mesh only modifies O(k log L/s) mesh simplices.

Finally, stability can be exploited to produce an efficient dynamic algorithm. Under the self-adjusting computation framework, with a small amount of additional effort, I show that the above algorithm can be dynamized to run in O(k log L/s) time per update, using O(n log L/s + m) space.

Thesis Committee:
Gary Miller, Chair
Anupam Gupta
Daniel Sleator
Umut A. Acar, Toyota Technological Institute at Chicago
Jonathan R. Shewchuk, University of California, Berkeley

Friday September 7th, 2007
WEH 7220

TITLE: Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

Kenneth L. Clarkson
IBM Research Labs, Almaden

ABSTRACT:

The problem of maximizing a concave function f(x) in a simplex S can be solved approximately by a simple greedy algorithm, that in k steps can find a point x_k such that f(x_k) ≥ f(x_*) - O(1/k), where f(x_*) is the maximum value of f in S. This algorithm and analysis were known before, and related to problems of statistics and machine learning, such as boosting, training support vector machines, regression, and density mixture estimation. In other work, coming from computational geometry, the existence of / ε-coresets/ was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm. Similar greedy algorithms, that are special cases of the Frank-Wolfe algorithm, were described for other enclosure problems. I’ll tie these results together, review some stronger convergence results, and generalize or strengthen some coreset bounds.

September 7, 2007
Tsz Hong Hubert Chan

10:30 AM, 4623 Wean Hall

Thesis Oral

Title: Approximation Algorithms for Bounded Dimensional Metric Spaces

Abstract:

The study of finite metrics is an important area of research, because of its wide applications to many different problems. The input of many problems (for instance clustering, near-neighbor query and network routing) naturally involves sets of points on which a distance function has been defined. Hence, one would be motivated to store and process metrics in an efficient manner. The central idea in metric embedding is to represent a metric space by a “simpler” metric space so that the properties of the original metric space is well preserved.

More formally, given a target class C of metrics, an embedding of a finite metric space M = (V,d) into the class C is a new metric space M’ = (V,d’) such that M’ is in C. Most of the work on embeddings has used distortion as the fundamental measure of quality; the distortion of an embedding is the worst multiplicative factor by which distances are increased by the embedding. In the theoretical community, the popularity of the notion of distortion has been driven by its applicability to approximation algorithms: if the embedding f: (V,d) -> (V,d’) has a distortion of D, then the cost of solutions to some optimization problems on (V,d) and on (V,d’) can only differ by some function of D; this idea has led to numerous approximation algorithms. Seminal results include the O(log n) distortion embeddings of arbitrary metrics into Euclidean spaces with O(log n) dimensions, and the fact that any metric admits an O(log n) stretch spanner with O(n) edges.

The theoretical results mentioned above are optimal. However, it is pessimistic in the sense that such guarantees hold for any arbitrary metric. It is conceivable that better results can be obtained if the input metrics are “simple”. The main theme of this work is to investigate notions of complexity for an abstract metric space and theoretical guarantees for problems in terms of the complexity of the input metric.

One popular notion for measuring the complexity of a metric is the doubling dimension, which restricts the local growth rate of a metric. We show that the results on spanners and embeddings can be improved if the given metrics have bounded doubling dimension. For instance, we give construction for constant stretch spanners with linear number of edges. Moreover, such metrics can be embedded into Euclidean space with O(log log n) dimensions and o(log n) distortion.

We also study a new notion of dimension that captures the global growth rate of a metric. Such a notion strictly generalizes doubling dimension in the sense that it places weaker restrictions on a given metric than those posed by doubling dimension. However, we can still obtain good guarantees for problems in which the objective depends on the global nature of the metric, an example of which is the Traveling Salesperson Problem (TSP). In particular, we give a sub-exponential time to solve TSP with approximation ratio arbitrarily close to 1 for such metrics.

Thesis Committee:
Anupam Gupta, Chair
Avrim Blum
R. Ravi
Kenneth L. Clarkson, IBM Research, Almaden