Title: Emerging trends in Optimization

In this talk we will present our views on likely future development paths in two pivotal areas of Optimization: 0-1 Integer Programming, and Linear Programming. Without any doubt, Integer Programming systems are now far more capable than they were only ten years ago -- problems that were once considered impossible can now be quickly solved. Some of this impressive progress is due to improvements in methodology, in particular, the introduction of branch-and-cut. But to a nontrivial degree, the improvements are also due to far faster computing machinery, and to vastly improved Linear Programming codes (which are used as a subroutine). The fundamental methodology in use in today's leading IP solvers was introduced more than forty years ago. This is an important point, because many intractable problems remain, and modern applications give rise to ever more complex, and far larger problems. The need for fundamentally new theory is quite clear. During the last ten years, a new body of work has emerged, pioneered by Lovasz and Schrijver, and Sherali and Adams, and more recently extended to a far greater degree by the work of Lasserre, Laurent, and the author. This work has resulted in a new approach to 0-1 Integer Programming, which, simultaneously, leads to algorithms with provably good properties, and furthermore, provides solid connections between Integer Programming and classical topics in pure mathematics, such as the mathematics underlying semidefinite programming. We will review this work and present some of the more recent results.

Linear Programming has also benefited, during the last decade, from a major stream of developments, both fundamental and computational. In conjunction with modern computers, the capabilities of today's best LP solvers is truly astounding. Nevertheless, difficult Linear Programs abound, for example in routing problems. Such applications are likely to generate astronomically large problem instances as we move into the next decade. The critical question is: do the standard LP solving methods now in use scale well? Computational experiments using very fast computers and the best LP solvers seem to indicate the answer to this question may well be a resounding NO. During the last decade, a new body of work has emerged from the theoretical computer science community. This work seeks to build approximate methods for Linear Programming that are, at once, provably good, and at the same time, "thrifty". This combination of theoretical effectiveness and cheap implementation bodes well for such methods, and computational experiments seem to agree with this view. We will review this area of work, and present computational results.

Title: Engineering Geometric Optimization Algorithms: Some Experiments

I will report on a few attempts at engineering simple geometric optimization algorithms. Both design considerations (flexibility, genericity, reusability, and programming techniques) and runtime will be presented.

Title: Subtraction in Geometric Searching

Designers of geometric algorithms have rarely been able to put subtraction, or, more generally, nonmonotone computation to good use. We discuss a variant of a classical range searching problem for which nonmonotonicity (ie, the ability to subtract and divide) provides added computational power. This is, to our knowledge, the only separation result between monotone and nonmonotone computation in geometric searching.

Title: Minimum Separation in Weighted Subdivisions

We will discuss a number of problems on computing the minimum separation between two regions of a planar triangulated weighted subdivision and present polynomial time results. The problems include the minimum one link weighted distance (a link is a line segment connecting the two regions) and the minimum one link d-width weighted distance (a link is a parallel strip of width "d" connecting the two regions). We give nontrivial, almost cubic upper bounds for these problems. The solutions involve a combination of geometric and mathematical optimization techniques. We will then show how to use some of these results to characterize a k-link shortest path and derive bounds on the length of such path. Some implications of these results in designing efficient approximation algorithms for computing k-link shortest paths in weighted subdivisions will also be addressed.

Title: Online Searching with Turn Cost

We consider the classic problem of searching for an object on a line (e.g., a bridge along a river) at an unknown distance from the original searcher position. It is well-known that a trajectory achieving the optimal competitive ratio of 9 consists of a geometric series that doubles its search depth at each step. An annoying feature of these trajectories is that there is no first step; instead they start with infinitesimal ``wiggling''. We show that this problem can be avoided by assuming a fixed turn cost $d$ for changing direction. We describe a strategy that is guaranteed to find the object while traveling at most 9OPT$ + 2d$, which is optimal in both the competitive ratio 9 and the additive penalty term $2d$. Our argument for upper and lower bound uses an infinite series of linear programs, which is interesting in its own right. Using the same approach, we give a tight analysis for the generalization to star search on $m$ rays.

This is joint work with S\'andor P. Fekete and Shmuel Gal.

Title: Touring a Sequence of Polygons

Given a sequence of $k$ polygons in the plane, a start point $s$, and a target point, $t$, we seek a shortest path that starts at $s$, visits in order each of the polygons, and ends at $t$. In the case that the polygons are disjoint and convex we give an algorithm running in time $O(kn\log (n/k) )$, where $n$ is the total number of vertices specifying the polygons. We also extend our results to the case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses $O(nk^2\log n)$ time. Our methods are simple and allow shortest path queries from $s$ to a query point $t$ to be answered in time $O(k\log (n/k))$. It is shown in the paper that for nonconvex polygons this ``touring polygons'' problem is NP-hard.

The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the {\em safari problem}: "find a shortest tour visiting a set of convex cages attached to the inside wall of a simple polygon" and the {\em watchman route problem} in a simple polygon: ''find a shortest tour that sees all points of the polygon''. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in $O(n^2\log n)$ time and the watchman route problem (through a fixed point $s$) in time $O(n^3\log n)$, compared with the previous time bounds of $O(n^3)$ and $O(n^4)$, respectively.

Additionally, our work is motivated by a cutting stock problem in which one must find an optimal cutting path for cutting polygonal parts from a sheet of material, while satisfying certain constraints.

Joint work with Moshe Dror, Anna Lubiw and Joseph S. B. Mitchell

Title: Quasiconvex Programming

Quasiconvex programming is a form of generalized linear programming in which one seeks a point minimizing the pointwise maximum of a set of quasiconvex functions. A simple example is the problem of finding the circumcenter of a discrete point set: the point minimizing the maximum distance to an input point. We describe applications of quasiconvex programming to mesh smoothing, brain flat mapping, hyperbolic graph drawing, polyhedral representation and symmetry display for planar graphs, conformal meshing, multi-projector tiled display color gamut equalization, and algorithm analysis; discuss the generalized linear approach to these problems and its shortcomings; and detail alternative numerical hill-climbing procedures for finding approximate solutions to quasiconvex programs.

Title: Constructing Spanners of Different Flavors

Given a set of n points S in the plane and a real value t>1 we show how to construct t-spanners of S with desirable properties. In particular we discuss how one can construct an initial spanner with some key properties which then can be pruned in time O(n log n) using a greedy approach to obtain a t-spanner with the additional properties that it has constant degree and small total weight.

Title: Shape Fitting with Outliers

Given a set H of n hyperplanes in Rd, we present an algorithm that eps-approximates the extent between the top and bottom k-levels of the arrangement of H in time O(n +(k/eps)^c), where c is a constant depending on d. The algorithm relies on computing a coreset of size O(k/eps^(d-1)) in near linear time, such that the k-level of the arrangement of the coreset approximates that of the original arrangement. Using this algorithm, we present efficient approximation algorithms for shape fitting with outliers, for various shapes. This is the first algorithm to handle outliers efficiently for the shape fitting problems considered.

Title: Leave no Stones Unturned: Improved Approximation
Algorithms for Degree-Bounded Minimum Spanning Trees

Given n points in the Euclidean plane, the degree-d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most d. For any arbitrary collection of points, we show that there always exists a degree-4 MST whose weight is at most (sqrt{2}+2)/3 times the weight of an MST. Our result improves the current best ratio of 1.143, due to Chan. Our algorithm starts with an MST and decreases the degrees of high degree nodes by local changes around it. Even though our improvement is marginal, our result assumes significance due to the fact that there are instances for which Chan's algorithm hits a snag and cannot obtain ratios any better than 1.143. By employing a smart charging scheme and a savings procedure, we are able to overcome the difficulties faced by Chan's algorithm. We do not believe that our ratio for degree-4 spanning trees can be improved unless a more global approach is considered, instead of just the local changes.

This is a joint work with Balaji Raghavachari.

Title: TSP with Neighborhoods of Varying Size

In TSP with neighborhoods we are given a set of objects in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Prior to this work constant-factor approximation algorithms have been known only for cases where the objects are of approximately the same size. We present a polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of arbitrary size. We also show that the problem is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.

Joint work with Mark de Berg, Joachim Gudmundsson, Christos Levcopoulos, Mark Overmars and Frank van der Stappen

Title: The Protein Side-Chain Positioning Problem

Determining the 3D positions of the side-chain atoms in a protein given a fixed backbone is an important subproblem of general protein structure prediction and has been the focus of a large body of research. The problem is NP-complete; in fact, it is inapproximable. In practice, it is tackled by a variety of general search techniques and specialized heuristics. We investigate a new formulation of the problem as a semidefinite program. We introduce two novel rounding schemes, and provide some theoretical justification for their effectiveness under various input conditions. We also present computational results on simulated data that show that our method outperforms a recently introduced linear programming approach on a wide range of inputs. Beyond the context of side-chain positioning, we are hopeful that our rounding schemes, which are very general, will be applicable elsewhere.

Joint work with Bernard Chazelle and Mona Singh.

Title: Approximate Protein Structural Alignment in Polynomial Time

Structural alignment of proteins is a fundamental problem in computational molecular biology. Its solution can help detect distant evolutionary relationships that are hard or impossible to discern from protein sequences alone. We present the problem along with an approximate polynomial time algorithm for this problem. Furthermore, we argue that approximate solutions are, in fact, of greater interest than exact ones, due to the noisy nature of the proteins' coordinates. Next the modeling of the problem is discussed and in particular we point out that a common alternative model, based on internal distance matrices, is significantly harder to solve. These observations can be used to develop new scoring functions whose optima can be approximated efficiently, and perhaps efficient algorithms for the multiple structural alignment problem. Lastly we look at the detailed behavior of the structural-alignment score for several pairs of proteins.

This is joint work with Nati Linial.

Title: Efficient Algorithms for Shared Camera Control

We consider a system that allows multiple networked users to share control over a robotic webcamera. Each user guides the camera pan, tilt and zoom, by drawing a rectangle in the user interface. The server adjusts the camera to best satisfy the user requests, by solving a geometric optimization problem that requires fitting one rectangle to many. We present an exact algorithm that improves upon previous results, as well as a simple near-linear time approximation algorithm.

Joint work with Sariel Har-Peled, Dezhen Song and Ken Goldberg.

Title: Approximation Algorithms for k-Center Clustering

We study the $k$-center problem for sets of points or balls. For the 1-center problem, using techniques of second-order cone programming and 'core-sets', we have developed $(1+\epsilon)$-approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. We also implement a simple $1+\epsilon$ approximation algorithm with running time $O(2^{1/\epsilon}dn)$ for $k$-center clustering for fixed dimensions (2 or 3) and small $k$ ($k \leq 5$) and show experimental results.

Joint Work with : Pankaj Kumar, Joseph S. B. Mitchell and Alper Yildirim

Title: Some Data Streaming Problems in Computational Geometry

There is an emerging paradigm of data streams where input is a high speed datafeed, and the goal is to compute within limited resources. I will discuss some geometric approximations---proximity problems, joins, facility location, etc.---with spatial datafeeds.

Title: Computing Projective Clusters via Certificates

In this talk I will review a few recent results on computing projective clusters. A central technique of these results is to first prove the existence of a small set of points, which we call certificates, so that the optimal solution over the certificates is a close approximation of the optimal solution for the entire set.

Title: Exact Parallel Algorithm for Computing Maximum Feasible Subsystems of Linear Relations

Given a system of linear inequalities, we consider the problem of finding a maximum feasible subsystem, that is a solution satisfying as many inequalities as possible. This general problem, called MAX FLS, is equivalent to the {\it Closed Hemisphere Problem}, which was shown to be NP-complete by Johnson and Preparata in 1978. Another equivalent geometric formulation is to find a face of the oriented hyperplane arrangement that is in the maximum possible number of positive halfspaces. Combinatorial abstraction of geometry simplifies further the problem by considering only the signvectors of the hyperplane arrangement. To compute MAX FLS we consider the equivalent geometric problem of finding the sign vector in a hyperplane arrangement with maximal number of nonnegative signs. We use a hyperplane arrangement construction algorithm which is memory efficient, highly parallelizable and output sensitive. i.e. polynomial in the size of input and output. This general hyperplane enumeration code can be adapted to solve the MAX FLS. To improve the time complexity for a given problem a branch-and-bound type technique is applied to eliminate unnecessary search. This makes the code adaptive, i.e. whose complexity depends on the problem at hand.

Joint work with K. Fukuda

Title: Geometric Optimization and Arrangements

This talk highlights the strong connection between geometric optimization and arrangements of curves and surfaces in computational geometry. Many problems in geometric optimization can be re-stated in terms of problems involving arrangements, and efficient solutions result by applying or adapting the rich machinery available in the theory of arrangements. A few examples that show these connections will be presented.

Title: Smoothed Analysis of Algorithms: Simplex Algorithm and Numerical Analysis

Theorists have been challenged by the existence of remarkable algorithms that are known by scientists and engineers to work well in practice, but whose theoretical analyses are negative or inconclusive. The root of the problem is that algorithms are usually analyzed in one of two ways: by worst-case or average-case analysis. The former can improperly suggest that an algorithm will perform poorly, while the latter can be overly optimistic because the random inputs it considers can bear little resemblance to those encountered in practice. We propose an analysis that we call smoothed analysis that can help explain the success of many algorithms that both worst-case and average-case cannot. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs. In particular, we consider Gaussian perturbations of inputs to algorithms that take real and complex inputs, and we measure the running time of algorithms in terms of the input size and the variance of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

The simplex algorithm is the classic example of an algorithm that performs well in practice but takes exponential time in the worst case. In the 1980's the simplex algorithm was shown to converge in expected polynomial time on various distributions of random inputs, most notably by Borgwardt and Smale. However, the last 20 years of research in probability and numerical analysis have taught us that these random instances have very special properties that one should not expect to find in practice.

For every matrix A with entries of absolute value at most 1, every vector c, and every vector b whose entries are 1 or -1, we show that the simplex algorithm using the shadow-vertex pivot rule takes expected time polynomial in 1/sigma and the sizes of A and c to solve:<

minimize c'x
s.t (A + \sigma G) x <= b

If A is well-scaled, then the solution to this program is an approximation to the original.

This is joint work with Daniel Spielman of MIT.

Title: Approximating the k-Radius of High-Dimensional Point Sets

The k-radius of a point set P with n points in d-dimensional Euclidean space is the minimum, over all k-dimensional flats F, of the distance from F to the furthest point in P from F. This problem is NP-hard in the high dimensional case even for k=1. The problem seems to be harder to approximate with increasing k. Recent work has uncovered polynomial time approximation schemes for fixed k (with running times depending only linearly on n*d) and polynomial time algorithms that give an O(log n) approximation for any k. In this talk, we will discuss the main ideas behind these algorithms.

Title: Random Walks and Geometric Algorithms

Random walks often lead to efficient sampling algorithms. Sampling algorithms, in turn, can be used to solve basic problems such as optimization and volume computation. The talk will survey recent results in the area, with a focus on geometric random walks.

Title: Streaming Geometric Optimization Using Graphics Hardware

Streaming algorithms have been a area of recent interest because of their relevance to dealing efficiently with large data sets. Much of the work in streaming has focused on computing statistical properties and approximations of data; notable examples are approximate quantiles, histograms of functions etc.

However, there has been little work on streaming in the context of geometric objects. For example, the diameter or bounding box is a fundamental extent measure of point sets: can we compute this in a streaming fashion ? We demonstrate that a wide variety of geometric optimization problems on point sets (diameter, bounding box, minimum enclosing ball, minimum width annulus) can be computed in a very restricted streaming model: that manifested by graphics hardware accelerator cards.

The results we provide are approximate (and in many cases provably so). Our algorithms provide a unified approach to dealing with a variety of optimization problems; from an implementation perspective, this is very valuable. Our implementations are also competitive (and in many cases far superior) to the best software implementations.

This is joint work with Pankaj Agarwal, Shankar Krishnan, and Nabil Mustafa.

Title: Hausdorff Distance under Translation for Points and Balls

We study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets $\A,\B$ of balls in $d$-dimensional space, $d=2,3$, and wish to find a translation $t$ that minimizes the Hausdorff distance between $\A+t$, the set of all balls in $\A$ shifted by $t$, and $\B$. We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). We consider either all possible translates $t$ (as is the standard approach), or consider only translations that keep the balls of $\A+t$ disjoint from those of $\B$. We propose several exact and approximation algorithms for these problems. Since the Hausdorff distance is sensitive to outliers, we also propose efficient approximation algorithms for computing the minimum root-mean-square (rms) and the minimum summed Hausdorff distance, under translation, between two point sets in $d$-dimensions. In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an $\eps$-approximation of the $1$-median of a set of points, under insertion and deletion.

Joint work with Pankaj K. Agarwal, Sariel Har-Peled, and Micha Sharir

Title:Unique Sink Orientations of Cubes and its Relations to Optimization

Consider (the edge graph of) an $n$-dimensional hypercube with its edges oriented so that every face has a unique sink. Such an orientation is called a unique sink orientation, and we are interested in finding the unique sink of the whole cube, when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges.

Unique sink orientations occur when the edges of a deformed geometric $n$-dimensional cube (i.e., a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Alan Stickney and Layne Watson), where orientations with cycles can arise. Similarly, linear programming and some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, are polynomial time reducible (in the unit cost model) to finding a sink in a unique sink orientation (possibly with cycles).

Recently a deterministic $O(1.61^n)$ procedure and a randomized algorithm with expected $O(1.44^n)$ vertex evaluations have been developed. An interesting aspect of these algorithms is that they do not proceed on a path to the sink (in a simplex-like fashion), but they exploit the potential of random access (in the sense of arbitrary access) to any vertex of the cube. The best known lower bound for deterministic methods is of the order $n^2 / \log n$.

Results by Bernd G\"artner, Ingo Schurr, Tibor Szab\'o and the speaker are presented.

Title: Approximate Minimum Volume Enclosing Ellipsoids Using Core Sets

Given a set S of n points in d-dimensional space, we study the problem of computing a $(1+\epsilon)$-approximation to the Minimum Volume Enclosing Ellipsoid of S. We establish the existence of a core set of size $O(d \log d + d/\epsilon)$. Combining this result with Khachiyan's algorithm, we devise an approximation algorithm that outputs a core set and an approximate minimum volume enclosing ellipsoid whose running time is $O(nd^2 \gamma + \gamma^{4.5} \log \frac{\gamma}{\epsilon})$, where $\gamma$ denotes the size of the core set. This result improves the previously known complexity results for large-scale instances with n >> d and reasonable values of $\epsilon$.

This is joint work with Piyush Kumar.