 |
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
|
|
