July - December 2011 Thematic Program on Discrete Geometry and Applications SEPTEMBER WORKSHOPS Talk title and abstract submissions

September 13-16, 2011 (Tuesday -Friday)
Workshop on Discrete Geometry

Jorge Luis Ramírez Alfonsín (Université Montpellier 2)
Matroid base polytope decomposition

Andras Bezdek (Auburn University)
On stability of polyhedra

We all have seen different versions of the popular children’s toy called ‘stand up kid’. These figures are easy to make as they are loaded figures which have only one stable equilibrium. Such bodies are called monostatic . The problem gets more interesting if one wants to make convex `stand up kids’ using homogeneous material. A recent construction of G.Domokos and P.Varkonyi amazed people and thus generated lot of media attention. Mathematically speaking they answered a question of V. Arnold by constructing a homogeneous, convex body (called Gomboc) which has exactly one stable equilibrium, exactly one unstable equilibrium and does not have any saddle type equilibrium.
From the very beginning the problem of finding a monostatic polyhedron with the smallest number of faces seemed to be of special interest. J.Conway and R.Guy (1969) constructed a monostatic polyhedron with 19 faces. It was long believed that 19 is the smallest such face number. In this talk, with a different idea, we construct a monostatic polyhedron which has only 18 faces. We also consider skeletal versions of the original stability problem. Among others we prove that if the 1, 2 and 3 skeletons of a tetrahedron is constructed of homogeneous material then it has at least two stable faces.

Adrian Dumitrescu (University of Wisconsin-Milwaukee)
Dispersion in disks

We present three new approximation algorithms with improved constant
ratios for selecting $n$ points in $n$ disks such that the minimum pairwise distance among the points is maximized.
1. A very simple $O(n\log n)$-time algorithm with ratio $0.511$ for disjoint unit disks.
2. An LP-based algorithm with ratio $0.707$ for disjoint disks of arbitrary radii that uses a linear number of variables and constraints, and runs in polynomial time.
3. A hybrid algorithm with ratio either $0.4487$ or $0.4674$ for (not necessarily disjoint) unit disks that uses an algorithm of Cabello in combination with either the simple $O(n\log n)$-time algorithm or the LP-based algorithm. The LP algorithm can be extended for disjoint balls of arbitrary radii in \RR^d, for any (fixed) dimension $d$, while preserving the features of the planar algorithm. The algorithm introduces a novel technique which combines linear programming and projections for approximating Euclidean distances. The previous best approximation ratio for dispersion in disjoint disks, even when all disks have the same radius, was $1/2$. Our results give a positive answer to an open question raised by Cabello, who asked whether the ratio $1/2$ could be improved.
Joint work with Minghui Jiang

Jack Edmonds (Istituto di Analisi dei Sistemi ed Informatica, Italy)
Partitions of the vertices by facets in simplicial polytopes, Nash equilibria, and domination in perfect digraphs

Ferenc Fodor (University of Szeged)
Approximations of spindle convex sets

We will discuss best and random approximations of spindle convex sets by convex disc-polygons. Spindle convex sets in the Euclidean plane are sets of circumradius not greater than one with the property that together with any pair of its points the set contains every short circular arc of radius at least one connecting these points. A convex disc-polygon is the intersection of a finite number of closed unit radius circular discs.
In this talk, we will prove sharp estimates of the order of convergence of best approximations of planar spindle convex sets by inscribed and circumscribed convex disc-polygons with respect to the Hausdorff metric, and the measures of deviation defined by perimeter and area differences. We will also discuss some aspects of random approximations of spindle convex sets by inscribed convex disc-polygons.
The results presented in this talk are joint with Viktor Vigh.

György Kiss (Eötvös Loránd University)
Notes on the illumination parameters of convex polytopes

Zsolt Lángi (Budapest University of Technology)
On a discrete isoperimetric inequality

Brass asked the following question in 2005: For n ? 5 odd, what is the maximum perimeter of a simple n-gon contained in a Euclidean unit disk? In 2009, Audet, Hansen and Messine answered this question, and showed that the optimal configuration is an isosceles triangle with a multiple edge, inscribed in the disk. In this note we give a shorter and simpler proof of their result, which we generalize also for hyperbolic disks, and for spherical disks of sufficiently small radii. Furthermore, we present results about other variants of the original question, and introduce some open problems.

Endre Makai (Alfréd Rényi Institute of Mathematics)
Stability of the Volume Product in the Plane

Horst Martini (University of Technology, Chemnitz)
Discrete geometry in normed planes

Benjamin Matschke (FU Berlin)
On the square peg problem

In 1911 Otto Toeplitz asked whether every simple closed curve in the plane contains the four vertices of a square. There exists many proofs for the special case of smooth curves, but the general case is still open. In this talk we present some progress, also on related problems.

Oliveros, Deborah
Helly Type Theorems in relation with Graph Theory

In this talk we will discuss a nice relation between Helly Type Theorems and the study of graphs and hypergraphs, particularly, how the chromatic number is related with some interesting problems in Discrete Geometry, such as some theorems for piercing and transversals to convex sets.

Pedro Sánchez (Universidad Nacional Autónoma de México)
Generating vertices for the row-column polytopes

Using a modification found by Vallejo and Avella of the RSK algorithm, it is possible to describe a Kronecker product $\chi^\lambda\otimes\chi^\mu\otimes\chi^\nu$ when $\nu$ is a two-part partition as a difference of the number of integral points contained on some sections of a family of polytopes.
These polytopes, having very high dimension and a large number of defining hyperplanes can be described by conventional geometric means only in the simplest cases. However using ideas from matroid theory, a method is developed to generate polytope vertices in the general case

Konrad Swanepoel (The London School of Economics and Political Science)
Dense favourite-distance digraphs

We reconsider the favourite distance problem introduced by Avis, Erdös and Pach some 20 years ago. In particular we give stability results and characterise the extremal situations in Euclidean spaces of dimensions 4 and higher. We also consider some other metric spaces where dense favourite distance digraphs occur.

Valeriu Soltan (George Mason University)
Carath´eodory-type Results for Faces of Convex Sets

Csaba Toth (University of Calgary)
Disjoint Compatible Geometric Matchings

We prove that for every even set of n pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al.. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees. (Joint work with Mashhood Ishaque and Diane Souvaine)

Gábor Fejes Tóth (Alfréd Rényi Institute of Mathematics)
Convex Sets in Empty Convex Position

---

September 19-23, 2011 (Monday -Friday)
Conference on Discrete Geometry and Optimization

David Avis (Kyoto University and McGill University)
The directed cut cone and polytope with mining applications

In this we give some results on the directed cut cone and polytope which are the positive hull and convex hull of all directed cut vectors of a complete directed graph, respectively. We present results on the polyhedral structure of these polyhedra. Our results were motivated by a problem in open pit mining that we will describe in the talk. (Joint work with Conor Meagher)

Christine Bachoc (Université Bordeaux 1)
Lower bounds for the measurable chromatic number of Euclidean space

Let $m_1({\mathbb R}^n)$ denote the measure of the largest subset of $\R^n$ not containing two points at distance one. There are essentially two methods to upper bound $m_1({\mathbb R}^n)$: the earlier goes back to Frankl and Wilson intersection theorems and employs finite sets of points with 0-1 coordinates. More recently F. Oliveira and F. Vallentin have proposed a different approach based on an (infinite dimensional) linear program. While the former leads to the best known asymptotic estimate, the later has improved the known results for small dimensions. After a discussion of these two methods we will present new improvements obtained with a combination of the two approaches. In turn, new improvements on the lower bounds for the measurable chromatic number are obtained.

Károly Bezdek (University of Calgary)
Contact numbers for congruent sphere packings

Continuing the investigations of [1] and [2] we study the following two open problems. Recall that the contact graph of an arbitrary finite packing of unit balls (i.e., of an arbitrary finite family of non-overlapping unit balls) in Euclidean 3-space is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if and only if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of a packing of n unit balls can have in Euclidean 3-space. Our method for finding lower and upper estimates for the largest contact numbers is a combination of analytic and combinatorial ideas and it is also based on some recent results on some classical problems on sphere packings. Finally, we are interested also in the following more special version of the above problem. Namely, let us imagine that we are given a lattice unit sphere packing with the center points forming the lattice L in Euclidean 3-space (and with certain pairs of unit balls touching each other) and then we wish to generate packings of n unit balls in such a special way that each and every center of the n unit balls is chosen from L. Just as in the general case we are interested in finding the largest possible contact number for the finite packings of n unit balls obtained in this way.
[1] K. Bezdek, On the maximum number of touching pairs in a finite packing of translates of a
convex body, J. Combin. Theory Ser. A 98/1 (2002), 192--200. [2] H. Harborth, Solution of Problem 664A, Elem. Math. 29 (1974), 14--15.

David Bremner (University of New Brunswick)
Orbitwise polyhedral representation conversion via fundamental domains

Jesús De Loera (University of California, Davis)
Integrals of polynomials over Convex Polytopes: Combinatorics and Algorithms

The volumes and integrals of over polyhedra are perhaps the most fundamental and basic concept in the history of mathematics. Already ancient civilizations worried about it (e.g., Egypt, Babylon) and we teach formulas for volumes of pyramids and cubes to K-6 students. Yet, volumes and integrals of convex polytopes are quite useful still today, from algebraic geometry to computer graphics, from combinatorics to probability and statistics.But, how does one go about actually computing an integral over a convex polytope if one cares to compute the number exactly? In this talk we survey why exact integral computation is relevant, why calculus techniques fail miserably for the goal of computation, and end with the latest results about efficient computation of integrals of polynomials over convex polytopes. If time allows I will demonstrate our new Software LattE Integrale.New results are joint work with: V. Baldoni, N. Berline, B. Dutra, M. Koeppe, M. Vergne.

Michel Deza (École Normale Supérieure & JAIST)
Spheric analogs of fullerenes

Jan Foniok (Queen's University)
Linear Complementarity, Unique-Sink Orientations and Oriented Matroids

The \emph{linear complementarity problem} (LCP) is for an input $n \times n$ real matrix~$M$ and an $n$-dimensional real vector~$q$ to ?nd non-negative vectors $w$ and~$z$ so that $w - M z = q$ and $w^T z = 0$. The latter \emph{complementarity condition} makes the problem non-linear. Chung proved that in general it is NP-hard to decide whether a solution exists. However, if (and only if) $M$~is a \emph{P-matrix}, i.e., all its principal minors are positive, then a unique solution exists for any~$q$. Finding this solution is a prominent computational problem with embarrassingly open complexity. Neither hardness results nor polynomial algorithms are known. Megiddo showed that the problem, for input~$M$,~$q$, to ?nd a solution~$w$,~$z$, or a certi?cate that $M$~is not a P-matrix, cannot be NP-hard unless NP${}={}$co-NP.
I will discuss two combinatorial tools for describing and analysing pivoting algorithms for the LCP: \emph{unique-sink orientations of hypercubes}, and \emph{complementary oriented matroids}. I will show conditions on these combinatorial structures that correspond to various subclasses of the class of P-matrices (such as K-matrices, hidden-K-matrices). These subclasses have been studied before and polynomial algorithms are known. Our setting provides a new, simpli?ed analysis of the algorithms.
Various results are joint work with Komei Fukuda, Bernd Gärtner, Lorenz Klaus, Hans-Jakob Lüthi and Markus Sprecher.

Fejes Tóth Lecture Series
Thomas C. Hales (University of Pittsburgh)

Lecture 1.
Mathematics in the Age of the Turing machine
Next year we celebrate the centennial of Alan Turing's birth. This will be a talk for a general audience about some of the ways that computers shape mathematical research. I will give examples of "computer proofs" that make computation part of the proof and "formal proofs" that use computers to check the logical reasoning behind proofs. I will also discuss the issue of the reliability of computers for mathematical research.

Lecture 2.
The weak and strong Dodecahedral Conjectures.
K. Bezdek has proposed a strong version of L. Fejes Tóth's classical dodecahedral conjecture. The conjecture states that the surface area of any Voronoi cell in a sphere packing in three dimensions is at least that of the regular dodecahedron. This lecture will describe a remarkably simple computer-assisted proof of the strong dodecahedral
conjecture.

Lecture 3.
Fejes Tóth's Contact Conjecture.
In 1969, L. Fejes Tóth made the following conjecture. In 3-space any packing of equal balls such that each ball is touched by twelve others consists of hexagonal
layers. This lecture will describe a recent computer-assisted proof of this conjecture.

Kim, Edward (Technische Universiteit Delft)
On diameters of transportation and network flow polytopes

Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos.

Matthias Köppe (University of California, Davis)
Intermediate sums on polyhedra: Ehrhart theory and an application in mixed integer optimization

We study intermediate sums, interpolating between integrals and discrete sums, which were introduced by A. Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comp. 75 (2006), 1449--1466]. For a given polytope P with facets parallel to rational hyperplanes and a rational subspace L, we integrate a given polynomial function h over all lattice slices of the polytope P parallel to the subspace L and sum up the integrals. We first develop an algorithmic theory of parametric intermediate generating functions. Then we study the Ehrhart theory of these intermediate sums, that is, the dependence of the result as a function of a dilation of the polytope. We provide an algorithm to compute the resulting Ehrhart quasi-polynomials in the form of explicit step polynomials. These formulas are naturally valid for real (not just integer) dilations and thus provide a direct approach to real Ehrhart theory. The algorithms are polynomial time in fixed dimension. Following A. Barvinok (2006), the intermediate sums also provide an efficient algorithm to compute, for a fixed number k, the highest k Ehrhart coefficients in polynomial time if P is a simplex of varying dimension. We also present an application in optimization, a new fully polynomial-time approximation scheme for the problem of optimizing non-convex polynomial functions over the mixed-integer points of a polytope of fixed dimension, which improves upon earlier work that was based on discretization [J.A. De Loera, R. Hemmecke, M. Köppe, R. Weismantel, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Math. Prog. Ser. A 118 (2008), 273--290]. The algorithm also extends to a class of problems in varying dimension. The talk is based on joint papers with Velleda Baldoni, Nicole Berline, Jesus De Loera, and Michele Vergne.

Monique Laurent (CWI)
Characterizing graphs with Gram dimension at most four

Given a graph $G=(V=[n],E)$, its {\em Gram dimension} $\GD(G)$ is the smallest integer $r\ge 1$ such that, for any $n\times n$ positive semidefinite matrix $X$, there exist vectors $p_i\in \oR^r$ ($i\in V$) satisfying $X_{ij}=p_i^Tp_j$ for all $ij\in V\cup E$.
The class of graphs with Gram dimension at most $r$ is closed under taking minors and clique sums. Clearly, $K_{r+1}$ is a minimal forbidden minor for membership in this class.We show that this is the only minimal forbidden minor for $r\le 3$ while, for $r=4$, there are two minimal forbidden minors: the complete graph $K_5$ and the octahedron $K_{2,2,2}$.These results are closely related to the characterization of Belk and Connelly (2007) for the class of $d$-realizable graphs with $d\le 3$. Recall that $G$ is {\em $d$-realizable} if, for any vectors $u_i$ ($i\in V$), there exist other vectors $v_i\in \oR^d$($i\in V$) satisfying $\|u_i-u_j\|_2=\|v_i-v_j\|_2$ for all $ij\in E$; that is, for any $n\times n$ Euclidean distance matrix, the distances corresponding to edges can be realized in $\oR^d$.Denoting by $\ED(G)$ the smallest integer $d$ such that $G$ is $d$-realizable,
the two parameters are related by $\GD(G)=\ED(\nabla G)$, where $\nabla G$ is the one-node suspension of $G$. Moreover,they satisfy: $\GD(\nabla G)=\GD(G)+1$ and $\ED(\nabla G)\ge \ED(G)+1$. Hence, $\GD(G)\ge \ED(G)+1$, so that our results imply those of Belk and Connelly.
Joint work with Antonis Varvitsiotis (CWI, Amsterdam).

Joseph S. B. Mitchell (State University of New York at Stony Brook)
Optimizing and Approximating Geometric Covering Tours

Oleg Musin (University of Texas at Brownsville)
Irreducible contact graphs and Tammes' problem

The Tammes problem is a problem in packing a given number N of equal circles on the surface of a sphere with their common radius as large as possible. The Tammes problem is presently solved only for several values of N: for N=3,4,6,12 by L. Fejes Toth (1943); for N=5,7,8,9 by Schutte and van der Waerden (1951); for N=10,11 by Danzer (1963); and for N=24 by Robinson (1961).
Recently, I and Alexey Tarasov solved the Tammes problem for N=13. This computer-assisted proof is based on an enumeration of maximal irreducible contact graphs with 13 vertices. Relying on these ideas, now we are working on properties of irreducible graphs, devoting special attention to maximal irreducible graphs for the Tammes and related problems.

Pablo A. Parrilo (Massachusetts Institute of Technology)
Convex graph invariants

The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this talk we discuss convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of a graph such as the maximum degree, the MAXCUT value (and its semidefinite relaxation), and spectral invariants such as the sum of the k largest eigenvalues. Such functions can be used to construct convex sets that impose various structural constraints on graphs, and thus provide a unified framework for solving a number of interesting graph problems via convex optimization. We give a representation of all convex graph invariants in terms of certain elementary invariants, and describe methods to compute or approximate convex graph invariants tractably. We also compare convex and non-convex invariants, and discuss connections to robust optimization. Finally we use convex graph invariants to provide efficient convex programming solutions to graph problems such as the deconvolution of the composition of two graphs into the individual components, hypothesis testing between graph families, and the generation of graphs with certain desired structural properties.

Vincent Pilaud (Fields Institute and Université Paris 7)
The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations, which generalize triangulations in two different ways, can both be interpreted via duality as pseudoline arrangements with contacts supported by a given network. In this talk, I will present the construction of the "brick polytope" of a sorting network. The graph of this polytope realizes a subgraph of the flip graph on pseudoline arrangements supported by the network. In particular, for certain well-chosen networks, our brick polytopes coincide with Hohlweg & Lange's associahedra. Joint work with Francisco Santos (Universidad de Cantabria).

Franz Rendl (University of Klagenfurt)
SDP and eigenvalue approaches to Bandwidth and Vertex-Separator problems in graphs
Authors: Abdel Lisser, Mauro Piacentini, Franz Rendl

Bandwidth and Separator Problems are in general NP-complete. A natural mathematical formulation of these problems leads to quadratic problems in binary variables. This leads naturally to SDP relaxations, and also to eigenvalue based relaxations. We consider relaxations based on eigenvalues. These are improved by redistributing the edge weights, leading to eigenvalue optimization problems. We present some preliminary computational results which indicate that this approach is feasible also for large scale problems.

Achill Schürmann (University of Rostock)
Exploiting Polyhedral Symmetries in Social Choice Theory

A vast amount of literature in social choice theory deals with quantifying the probability of certain election outcomes. This is in particular the case for so-called ``voting paradoxes''. One way of computing the probability of a specific voting situation is via counting integer points in associated polyhedra. Here, Ehrhart theory can help, but unfortunately the dimension and complexity of the involved polyhedra grows rapidly with the number of candidates. However, if we exploit available polyhedral symmetries, some computations become possible that otherwise seem infeasible. We exemplarily show this in two very well known examples: Condorcet's paradox and in plurality voting vs plurality runoff.

Anthony Man-Cho So (The Chinese University of Hong Kong)
Rigidity and Localization: An Optimization Perspective

A fundamental problem in wireless ad-hoc and sensor networks is that of determining the positions of sensor nodes. Often, such a problem is complicated by the presence of nodes whose positions cannot be uniquely determined. Most existing work uses the notion of global rigidity from rigidity theory to address the non-uniqueness issue. However, such a notion is not entirely satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the problem of determining the node positions is still intractable in general. In this talk, we propose to use the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the network localization problem. Specifically, we show that both the problem of deciding whether a given network localization instance is universally rigid and the problem of determining the node positions of a universally rigid instance can be solved efficiently using semidefinite programming (SDP). These results can be viewed as sufficient conditions for a certain SDP to have a unique low rank solution. Then, we give various constructions of universally rigid instances. In particular, we show that trilateration graphs are generically universally rigid, thus demonstrating not only the richness of the class of universally rigid instances, but also the fact that trilateration graphs possess much stronger geometric properties than previously known. Based on the theory, we introduce an edge sparsification procedure that can provably preserve the localizability of the original input, but the SDP problem size is greatly reduced.

Tamon Stephen (Simon Fraser University)
The width of 4-prismatoids

Santos' recent construction of a counterexample to the Hirsch conjecture highlights a particular 5-dimensional "prismatoid" polytope. We use the Euler characteristic to prove that there is no analogous 4-dimensional prismatoid.
This is joint work with Francisco Santos and Hugh Thomas.

Frank Vallentin (Technische Universiteit Delft)
Spectral bounds for the independence number and the chromatic number of an operator

We extend the definition of the chromatic number and the independence number of finite graphs (and their adjacency matrices) to bounded, symmetric operators on Hilbert spaces. Furthermore, we extend results by Hoffman and Lovasz showing that the knowledge of the spectrum of the operator gives lower and upper bounds. This provides a theoretical framework in which many packing and coloring problems for finite and infinite graphs can be conveniently studied with the help of harmonic analysis and convex optimization. We apply it to infinite graphs on the unit sphere, to infinite graphs on Euclidean space, and to limits of graphs.

Yuan Yao (PKU)
A Geometric Approach to Social Choice: Combinatorial Hodge Theory

With the rapid development of internet, preference aggregation over networks has become an increasingly important field which enables various crowdsourcing experiments on social choice. Here we present a novel perspective to preference aggregation or social choice, based on combinatorial Hodge theory, whose classical theory is a milestone connecting differential geometry and algebraic topology.

Yinyu Ye (Stanford University)
Universal Rigidity Theory and Semidefinite Programming for Sensor Network Localization

A fundamental problem in wireless ad–hoc and sensor networks is that of determining the positions of sensor nodes. Often, such a problem is complicated by the presence of nodes whose positions cannot be uniquely determined. Most existing work uses the notion of global rigidity from rigidity theory to address the non–uniqueness issue. However, such a notion is not entirely satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the problem of determining the node positions is still intractable in general. In this talk, we propose to adapt the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the network localization problem. Specifically, we show that both the problem of deciding whether a given network localization instance is universally rigid and the problem of determining the node positions of a universally rigid instance can be solved efficiently using semidefinite programming (SDP). Then, we give various constructions of universally rigid instances. In particular, we show that trilateration graphs are universally rigid for all instances in general positions, thus demonstrating not only the richness of the class of universally rigid instances, but also the fact that trilateration graphs possess much stronger geometric properties than previously known.

---

September 26-29, 2011 (Monday - Thursday)
Workshop on Optimization

Miguel Anjos (École Polytechnique de Montréal)
Valid Polynomial Inequality Generation in Polynomial Optimization

Polynomial optimization problems are normally solved using hierarchies of convex relaxations. These schemes rapidly become computationally expensive, and are usually tractable only for problems of small sizes. We propose a novel dynamic scheme for generating valid polynomial inequalities for general polynomial optimization problems. These valid inequalities are then used to construct better approximations of the original problem. For the special case of binary polynomial problems, we prove that the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the problem. We also present examples illustrating the computational behavior of the scheme and compare it to other methods in the literature.

Kurt M. Anstreicher (University of Iowa)
An Approach to the Dodecahedral Theorem Based on Bounds for Spherical Codes

The dodecahedral theorem states that in a packing of unit spheres in R^3, the Voronoi cell of minimum possible volume is a regular dodecahedron with inradius one. The theorem was conjectured by Fejes Toth in 1943, and proved by Hales and McLaughlin in 1998 using techniques developed by Hales for his proof of the Kepler conjecture. The proof of Hales and McLauughlin, while apparently correct, is difficult to verify due to the many cases and extensive computations required. In his 1964 book Regular Figures, Fejes Toth suggested a possible proof for the dodecahedral theorem but was unable to verify a key inequality. We describe an approach to completing Fejes Toth's proof that uses strengthened bounds for spherical codes.

Antoine Deza (McMaster University)
A further generalization of the colourful Carathéodory theorem

Given d+1 sets, or colours, S_1,S_2,...,S_(d+1) of points in R^d, a colourful set is a set S containing at most one point from each S_i for i = 1,...,d+1. The convex hull of a colourful set S is called a colourful simplex. Bárány’s colourful Carathéodory theorem asserts that if the origin 0 is contained in the convex hull of S_i for i = 1,...,d +1, then there exists a colourful simplex containing 0. The sufficient condition for the existence of a colourful simplex containing 0 was generalized to 0 being contained in the convex hull of (S_i U S_j) for 1 ? i < j ? d+1 by Arocha et al. and by Holmsen et al. We further generalize the theorem by showing that a colourful simplex containing 0 exists under weaker conditions. A slightly stronger version of this new colourful Carathéodory theorem is also given. This result provides a short and geometric proof of the previous generalization of the colourful Carathéodory theorem. We also give an algorithm to find a colourful simplex containing 0 under the generalized condition. In the plane an alternative and more general proof using graphs is given. In addition, we observe that, in general, the existence of one colourful simplex containing 0 implies that the number of such simplices is at least the size of the smallest S_i. In other words, any condition implying the existence of a colourful simplex containing 0 actually implies that the number of such simplices is at least the size of the smallest S_i.
Joint work with Frédéric Meunier

György Dósa (University of Pannonia)
Online reassignment models (in scheduling)

In scheduling, online reassignment means, that during the online scheduling process, some jobs can be reassigned from one machine to another (in a bounded way), or a buffer can be used which can store temporarily some jobs, or at the end of the scheduling process some jobs can be reassigned. Clearly, this is some kind of semi-online scheduling. The option of reassignment makes the scheduling problem to be better handable; if we measure the goodness of an algorithm with competitive ratio (which is some kind of worst case preformance ratio), this means that the semi online condition decreases the competitive ratio what can be reached by an (optimal) algorithm. We treat and compare to each other some such reassignment conditions in case of a (fundamental) scheduling problem.

Robert M. Freund (Massachusetts Institute of Technology)
Design of Photonic Crystals with Multiple and Combined Band Gaps, plus Fabrication-Robust Design
Authors: Robert Freund (presenter), Abby Men, N. Cuong Nguyen, Pablo Parrilo, Jaime Peraire

Our concern is with optimal design of photonic crystals with large band-gaps, thereby enabling a wide variety of prescribed interaction with and control of mechanical and electromagnetic waves. We present and use an algorithm based on convex conic optimization to design two-dimensional photonic crystals with large absolute band gaps. Our modeling methodology yields a series of finite-dimensional eigenvalue optimization problems that are large-scale and non-convex, with low regularity and non-differentiable objective. By restricting to appropriate eigen-subspaces, we reduce the problem to a sequence of small-scale convex semidefinite programs (SDPs) for which modern SDP solvers can be efficiently applied. Among several illustrations we show that it is possible to design photonic crystals which exhibit multiple absolute band gaps for the combined transverse electric and magnetic modes. The optimized crystals show complicated patterns which are far different from existing photonic crystal designs. We employ subspace approximation and mesh adaptivity to enhance computational efficiency. The resulting optimized structures are not necessarily fabricable, due to lack of connectedness of the materials and/or complicated boundary structure. We introduce new modeling methods to address the issue of optimizing designs that yield tractable models and yet are robust in the context of fabricability.

Jon Lee (University of Michigan)
Submodular-function maximization

Submodular-function maximization is a central unifying model in combinatorial optimization. Applications range from practical problems such as reconfiguring an environmental monitoring network, to more stylized problems such as the graph max-cut problem. I will describe some of the motivating applications, survey some different methodologies for maximizing a submodular function subject to side constraints, and describe computational results on environmental-monitoring problem instances for some of the more practical algorithms. Interestingly, while some of the algorithms are aimed at practical computation via an Operations Research / Mathematical Optimization approach, and others are driven by the Computer Science theory of approximation algorithms, there is significant common ground.

Adrian Lewis (Cornell University)
Nonsmooth optimization and semi-algebraic sets

Concrete optimization problems, while often nonsmooth, are not pathologically so. The class of "semi-algebraic" sets and functions - those arising from polynomial inequalities - nicely exemplifies nonsmoothness in practice. Semi-algebraic sets (and their generalizations) are common, easy to recognize, and richly structured, supporting powerful variational properties. In particular I will discuss a generic property of such sets - partial smoothness - and its relationship with a proximal algorithm for nonsmooth composite minimization, a versatile model for practical optimization.

Gabor Pataki (University of North Carolina)
Bad semidefinite programs: they all look the same

Duality theory is a central concept in Semidefinite Programming (SDP), just like it is in linear programming, since in optimization algorithms a dual solution serves as a certificate of optimality. However, in SDP, unlike in LP, ``pathological'' phenomena occur: nonattainment of the optimal value, and positive duality gaps between the primal and dual problems.
Motivated by the curious similarity of pathological SDP instances appearing in the literature, we find an exact characterization of semidefinite systems, which are badly behaved from the viewpoint of duality, i.e. show ``all bad SDPs look the same''. We also prove an "excluded minor" type result: all badly behaved semidefinite systems can be reduced (in a well defined sense) to a minimal such system with just one variable, and two by two matrices. More generally, we find characterizations of badly behaved conic linear systems over a general closed convex cone.

Javier Peña (Carnegie Mellon University)
A modified perceptron algorithm

The perceptron algorithm, introduced in the late fifties in the machine learning community, is a simple greedy algorithm for solving the polyhedral feasibility problem $Ay > 0$. The algorithm's main advantages are its simplicity and noise tolerance. The algorithm's main disadvantage is its slow convergence rate. We propose a modified version of the perceptron algorithm that retains the algorithm's
original simplicity but has a substantially improved convergence rate. This is joint work with doctoral student Negar Soheili at Carnegie Mellon.

Istvan Szalkai (University of Pannonia)
Counting Chemical Reactions and Simplexes in R^n

Michael J. Todd (Cornell University)
A Robust Robust Optimization Result and the Probability that a Random Triangle is Acute

After reviewing a result on the (lack of) sensitivity of the optimal value to a misspecification of the objective function coefficients, we give a short proof of a result of Edelman and Strang that the probability that a random triangle is acute is 1/4.

Kim-Chuan Toh (National University of Singapore)
A proximal point method for matrix least squares problem with nuclear norm regularization

We consider a proximal point method for solving the nuclear norm regularized matrix least squares problem with equality and inequality constraints. We show that the soft thresholding operator is strongly semismooth everywhere. For the inner subproblems, due to the presence of inequality constraints, we reformulate the problem as a system of semismooth equations. Then an inexact smoothing Newton method is proposed to solve this reformulated semismooth system. At each iteration, we apply the BiCGStab iterative solver to obtain an approximate solution to the generated smoothing Newton linear system. Numerical experiments on a variety of large scale matrix least squares problems, where the matrices involved have some special structures, show that the proposed proximal point method is very efficient.

Levent Tunçel (University of Waterloo)
Geometric Representations of Graphs, Semidefinite Optimization and Min-Max Theorems

We start with a result of Lov\'{a}sz relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish close relationships among many related graph parameters, to establish min-max theorems and to translate results related to one of the graph parameters above to all the others. We also revisit some classical concepts in tensegrity theory and utilize them to interpret the dual SDPs for a wide class of geometric graph representations. This talk is based on joint work with Marcel Carli Silva.

Stephen A. Vavasis (University of Waterloo)
Finding Low-Rank Submatrices with Nuclear Norm and l1-Norm

We propose a convex optimization formulation using nuclear norm and l1-norm to find a large low-rank submatrix for a given matrix. We are able to characterize the low-rank and sparsity structure of the resulting solutions. We show that our model can recover low-rank submatrices for matrices with subgaussian random noises. We solve the proposed model using a proximal point algorithm and apply it to an application in image feature extraction.
Joint work with X. V. Doan of Waterloo and Warwick

Hayato Waki (The University of Electro-Communications, Tokyo)
On a smaller SDP relaxation for polynomial optimization

Polynomial optimization problems (POP) is the problem of minimizing a polynomial  objective function over the set defined by polynomial equalities and/or inequalities. It is well-known that finding the global optimal value of POP is NP-hard. Lasserre and Parrilo independently proposed SDP approaches to find a tighter lower bound of the global value of POP. However, the resulting SDP relaxation problems often become too large-scale to solve. To recovery this difficulty, we propose a smaller SDP relaxation. We show that  our SDP relaxation converges to the global optimal value if the objective function has a small perturbation with higher order.  In our SDP relaxation, we do not add  a small perturbation explicitly, but exploit numerical errors in the practical computation of primal-dual interior-point methods as perturbation in the objective function. We also present some numerical results and show the computational efficiency. This is a joint work with Masakazu Muramatsu.

Henry Wolkowicz (University of Waterloo)
Efficient Solutions for the Large Scale Trust Region Subproblem

The \emph{Trust Region Subproblem} (TRS) is the: minimization of a quadratic (possibly non-convex) function over a sphere. It is the main step of the trust region method for unconstrained optimization, and is a basic tool behind regularization. The TRS has interesting theoretical properties as it is an implicit convex problem. Many efficient algorithms have been proposed and implemented.
In particular, current algorithms can exploit sparsity for large scale problems; and, they can also handle degeneracy, i.e., the so-called \emph{hard case}. In this paper we show that a \emph{shift and deflate} approach changes the hard case into a trivial case. Thus the TRS is one instance of a class of problems where one can take advantage of degeneracy once the structure is well understood. We add the above approach to several additional techniques and derive an efficient algorithm for solving large scale instances of TRS.

Yuriy Zinchenko (University of Calgary)
Shrink-Wrapping trajectories for Linear Programming

Hyperbolic Programming (HP) --minimizing a linear functional over an affine subspace of a finite-dimensional real vector space intersected with the so-called hyperbolicity cone-- is a class of convex optimization problems that contains well-known Linear Programming (LP). In particular, for any LP one can readily provide a sequence of HP relaxations. Based on these hyperbolic relaxations, a new Shrink-Wrapping approach to solve LP has been proposed by Renegar. The resulting Shrink-Wrapping trajectories, in a sense, generalize the notion of central path in interior-point methods. We study the geometry of Shrink-Wrapping trajectories for Linear Programming. In particular, we analyze the geometry of these trajectories in the proximity of the so-called central line, and contrast the behavior of these trajectories with that of the central path for some pathological LP instances.

---

Back to top