2010 CMS Summer Meeting
University of New Brunswick (Fredericton), June 4 - 6, 2010

Geometric and Combinatorial Aspects of Convex Optimization
Org: David Bremner (UNB)

KAROLY BEZDEK, University of Calgary, 2500 University Drive NW, Calgary, AB
From illuminating ball-polyhedra to minimizing the volume of spherical sets of constant width

Ball-polyhedra are intersections of finitely many congruent balls in Euclidean space. The ball-polyhedron is called a "fat" one, if it contains the centers of its generating balls. The core part of this talk is an extension of Schramm's theorem and its proof on illuminating convex bodies of constant width to the family of "fat" ball-polyhedra.

DAVID BREMNER, University of New Brunswick
Finding extreme rays via the fundamental domain

A fundamental domain of geometric object X is a minimal subset D such that the object can be covered by isomorphs of D under the natural symmetry group of X. For a convex polyhedral cone we have the property that every orbit of extreme rays has exactly one representative in a given fundamental domain. In this talk I will present some ideas and preliminary experiments for computing orbits of extreme rays of convex cones, via computing (approximately) a fundamental domain of the cone.

MICHAEL BURR, Courant Institute / New York University, 251 Mercer St., New York, NY 10012, USA
Dynamic Maintenance of Half-Space Depth and Contours

Half-space depth (or Tukey depth) is one of the most commonly studied data depth measures because it enjoys many desirable properties for data depth functions (in both the sample and continuous cases). The data depth contours bound regions of increasing depth. For the sample case, there are two competing definitions of contours: the rank-based contours and the cover-based contours.

In this talk, I will present three dynamic algorithms for maintaining the half-space depth of points and contours: the first maintains the half-space depth of a single point in a data set in O(logn) time per update (insertion/deletion) and overall linear space. A corollary of this result will be a strong structural result on the behavior of dynamic cover-based contours near data points, which is of independent interest. By maintaining a data structure for each data point, I will present an algorithm for dynamically maintaining the rank-based contours in O(n·logn) time per update and overall quadratic space. Finally, the third dynamic algorithm maintains the cover-based contours in O(n·log2 n) time per update and overall quadratic space.

DAN CHEN, Carleton University, Ottawa, ON
Absolute Approximation of Tukey Depth: Theory and Experiments

A Monte Carlo approximation algorithm for the Tukey depth problem in high dimensions is introduced. The algorithm is a generalization of an algorithm presented by Rousseeuw and Struyf (1998). The performance of this algorithm is studied both analytically and experimentally.


A point pRd has simplicial depth q relative to a set S if it is contained in q closed simplices generated by (d+1) sets of S. More generally, we consider colourful simplicial depth, where the single set S is replaced by (d+1) sets, or colours, S1,...,Sd+1, and the colourful simplices containing p are generated by taking one point from each set. Assuming that the convex hulls of the Si's contain p in their interior, Bárány's colourful Carathéodory's Theorem (1982) shows that p must be contained in some colourful simplex. We are interested in determining the minimum number of colourful simplices that can contain p for sets satisfying these conditions. That is, we would like to determine μ(d), the minimum number of colourful simplices drawn from S1,...,Sd+1 that contain pRd given that pint( conv(Si) ) for each i. Without loss of generality, we assume that the points in ∪i Si ∪{p} are in general position. The quantity μ(d) was investigated in [3], where it is shown that 2d ≤ μ(d) ≤ d2+1, that μ(d) is even for odd d, and that μ(2)=5. This paper also conjectures that μ(d) = d2+1 for all d ≥ 1. Subsequently, Bárány and Matousek (2007) verified the conjecture for d=3 and provided a lower bound of μ(d) ≥ max(3d, [(d(d+1))/5] ) for d ≥ 3, while Stephen and Thomas (2008) independently provided a lower bound of μ(d) ≥ [((d+2)2)/4] . We show that for d ≥ 1, we have μ(d) ≥ [((d+1)2)/2] . This strengthens the previously known lower bounds for all d ≥ 4.

Joint work with Tamon Stephen (Simon Fraser) and Feng Xie (McMaster).

WILLIAM HUA, McMaster University, 1280 Main Street West, Hamilton, ON
More bounds on the diameters of convex polytopes

Let ∆(d,n) be the maximum possible edge diameter over all d-dimensional polytopes defined by n inequalities. The Hirsch conjecture, formulated in 1957, suggests that ∆(d,n) is no greater than nd. No polynomial bound is currently known for ∆(d,n), the best one being quasi-polynomial due to Kalai and Kleitman in 1992. Goodey showed in 1972 that ∆(4,10)=5 and ∆(5,11)=6, and more recently, Bremner and Schewe showed ∆(4,11) = ∆(6,12) = 6. In this follow-up, we show that ∆(4,12)=7 and present strong evidence that ∆(5,12) = ∆(6,13) = 7.

Joint work with David Bremner, Antoine Deza and Lars Schewe.

EDWARD KIM, University of California, Davis
An update on the Hirsch Conjecture

The Hirsch conjecture was posed in 1957 in a letter from Warren M. Hirsch to George Dantzig. It states that the graph of a d-dimensional polytope with n facets cannot have diameter greater than nd. Despite being one of the most fundamental, basic and old problems in combinatorial geometry and optimization, what we know is quite scarce. Most notably, not even a polynomial upper bound is known for the diameters that are conjectured to be linear. In contrast, very few polytopes are known where the bound nd is attained. We survey results on both the positive and on the negative side of the conjecture.

CONOR MEAGHER, McGill University, Montreal, Quebec
Structural Properties of the Directed Cut Polytope

While much is known about the structural properties of the cut cone and polytope and their relaxations the metric cone and polytope, little is known about the directed cut equivalents.

The directed cut polytope (resp. cone) is the convex hull (resp. positive hull) of the arc incidence vectors of the directed cuts of the complete digraph. We present some structural properties of the directed cut cone and polytope, and their natural relaxations, the directed metric cone and polytope. In particular, it is shown that the directed cut polytope (resp. cone) is the convex (resp. positive) hull of two cut polytopes (resp. cones). New facets of the directed cut polytope are presented based on bijections from well known facets of the cut polytope.

Structural results on the projection of the directed cut polytope and cone onto the arc set of an arbitrary digraph G will also be presented. In particular facet preserving operations will be discussed, including directed version of triangular elimination and zero-lifting.

MEGAN OWEN, North Carolina State University, Box 8205, Raleigh, NC 27695
Averages in the space of phylogenetic trees

The space of metric phylogenetic trees is a polyhedral complex, as constructed by Billera, Holmes, and Vogtmann (2001). This space is also non-positively curved, so there is a unique shortest path between any two trees and a well-defined notion of an average or mean trees for a given set of trees. Finding either of these is a convex optimization problem. We will describe how a polynomial time algorithm for computing the shortest path can be used in computing the mean tree. We will also discuss how the mean tree can be used in some applications, such as reconstructing species trees from gene trees and comparing the topology of blood vessels in the brain.

Joint work with Ezra Miller (Duke) and Scott Provan (UNC).

Basis Reduction, and the Complexity of Branch-and-Bound

Branch-and-bound is a classical method to solve integer programming feasibility problems. On the theoretical side, it is considered inefficient: it can provably take an exponential number of nodes to prove the infeasibility of a simple integer program. In this work we show that branch-and-bound is theoretically efficient, if we apply a simple transformation in advance to the constraint matrix of the problem which makes the columns short and near orthogonal. We analyze two such reformulation methods, called the rangespace and the nullspace methods. We prove that if the coefficients of the problem are drawn from {1,...,M} for a sufficiently large M, then for almost all such instances the number of subproblems that need to be enumerated by branch-and-bound is at most one. Besides giving an analysis of branch-and-bound, our main result generalizes results of Lagarias and Odlyzko, Frieze, and Furst and Kannan on the solvability of subset sum problems to bounded integer programs.

We give some numerical values of M which make sure that 99 percent of the reformulated problems solve at the rootnode. These values turned out to be surprisingly small for moderate values of n (the number of variables), and m (the number of constraints).

We also report the results of a computational study showing that branch-and-bound can efficiently solve subset sum problems with huge coefficients, that arise from cryptographic applications.

Joint work with Mustafa Tural at IMA, and Erick B. Wong at UBC.

DIANE SOUVAINE, Tufts University, Medford, MA 02155, USA
Computational Geometry and Statistical Depth Functions

Over the past twenty years, statisticians have developed the concept of data depth as a method of multivariate data analysis that requires no prior assumptions on the probability distribution of the data and that handles outliers. Proposed data depth metrics are inherently geometric, with a numeric value assigned to each data point that represents its centrality within the given data set. It is then possible to create depth contours that bound the sets of points all having a depth higher than some set of fixed thresholds and use these contours for analysis and visualization of the (presumably large) data set.

Data depth remains a relatively new field. A number of data depth measures have been defined and analysed, and new data depth measures continue to be proposed. Algorithmic and combinatorial techniques from computational geometry are used to develop more efficient tools for data-depth analysis. This talk will provide an overview of some of the standard data depth measures such as halfspace depth, simplicial depth, regression depth, L1 depth, and proximity graph depth. It will also discuss a set of desirable properties for data depth functions, describe enhancements of some of the standard measures to address some previous weaknesses, and provide a framework for evaluating current and future depth functions.

CSABA TOTH, University of Calgary, Calgary, Alberta, Canada
Containment queries for colorful simplices

A simplex spanned by a colored point set S in Euclidean d-space is colorful if all vertices have distinct colors. The union of all full-dimensional colorful simplices is the colorful union, denoted by U(S). We show that the maximum combinatorial complexity of the colorful union for n points in d-space is Ω(n(d−1)2). We prove several structural properties of the colorful union. In particular, U(S) is the union of d+1 star-shaped polyhedra, which leads to efficient data structures for point inclusion queries in U(S). To illustrate the difficulty of working with the colorful union, we construct colored point sets S of size n in 3-space with some pathological features.

Joint work with André Schulz (MIT).

CHRISTOPHE WEIBEL, McGill University, Burnside Hall, 805 Sherbrooke West, Montreal, QC
Maximal f-vectors of Minkowski sums of large numbers of polytopes

It is known that in the Minkowski sum of r polytopes in dimension d, with r < d, the number of vertices of the sum can potentially be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far.

In this talk, I study polytopes in general orientations, and I show that the number of faces of a sum of r polytopes in dimension d, with rd, is linearly related to the number of faces in sums of less than d of the summand polytopes. We can deduce from this exact formula a tight bound on the maximum possible number of vertices of the Minkowski sum of any number of polytopes in any dimension. In particular, the linear relation implies that a sum of r polytopes in dimension d, where summands have n vertices in total, has less than ((n) || (d−1)) vertices, even when rd.

HENRY WOLKOWICZ, University of Waterloo, Waterloo, Ontario
Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization

Wireless sensor networks have many applications, e.g., in monitoring physical or environmental conditions (temperature, sound, vibration, pressure, battlefield surveillance, home automation, hospital patients, traffic control, etc.). The sensor network localization, SNL, problem consists of locating the positions of ad hoc wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). One main point is to view SNL as a (nearest) Euclidean Distance Matrix, EDM, completion problem that does not distinguish between the anchors and the sensors. We show that there are advantages for using the well-studied EDM model. This problem can be relaxed to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem. This relaxation is ill-conditioned in two ways. First, it is, implicitly, highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone. This means that the Slater constraint qualification fails. Second, nonuniqueness of the optimal solution results in large sensitivity to small perturbations in the data.

The degeneracy in the SDP arises from cliques in the graph of the SNL problem. We take advantage of the absence of the Slater constraint qualification and derive a preprocessing technique that solves the SNL problem. With exact data, we explicitly solve the corresponding SDP problem without using any SDP solver. We do this by finding explicit representations of the faces of the SDP cone corresponding to intersections of cliques of the SNL problem. For problems with noise, we first solve nearest matrix problems to get best EDM approximations.

Joint work with Nathan Krislock.

Event Sponsors

AARMS: Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences

© Canadian Mathematical Society :