Ebook: Discrete Geometry and Optimization

​Optimization has long been a source of both inspiration and applications for geometers, and conversely, discrete and convex geometry have provided the foundations for many optimization techniques, leading to a rich interplay between these subjects. The purpose of the Workshop on Discrete Geometry, the Conference on Discrete Geometry and Optimization, and the Workshop on Optimization, held in September 2011 at the Fields Institute, Toronto, was to further stimulate the interaction between geometers and optimizers. This volume reflects the interplay between these areas.

The inspiring Fejes Tóth Lecture Series, delivered by Thomas Hales of the University of Pittsburgh, exemplified this approach. While these fields have recently witnessed a lot of activity and successes, many questions remain open. For example, Fields medalist Stephen Smale stated that the question of the existence of a strongly polynomial time algorithm for linear optimization is one of the most important unsolved problems at the beginning of the 21st century. The broad range of topics covered in this volume demonstrates the many recent and fruitful connections between different approaches, and features novel results and state-of-the-art surveys as well as open problems.

---

??Optimization has long been a source of both inspiration and applications for geometers, and conversely, discrete and convex geometry have provided the foundations for many optimization techniques, leading to a rich interplay between these subjects. The purpose of the Workshop on Discrete Geometry, the Conference on Discrete Geometry and Optimization, and the Workshop on Optimization, held in September 2011 at the Fields Institute, Toronto, was to further stimulate the interaction between geometers and optimizers. This volume reflects the interplay between these areas.

The inspiring Fejes Toth Lecture Series, delivered by Thomas Hales of the University of Pittsburgh, exemplified this approach. While these fields have recently witnessed a lot of activity and successes, many questions remain open. For example, Fields medalist Stephen Smale stated that the question of the existence of a strongly polynomial time algorithm for linear optimization is one of the most important unsolved problems at the beginning of the 21st century. The broad range of topics covered in this volume demonstrates the many recent and fruitful connections between different approaches, and features novel results and state-of-the-art surveys as well as open problems.

---

??Optimization has long been a source of both inspiration and applications for geometers, and conversely, discrete and convex geometry have provided the foundations for many optimization techniques, leading to a rich interplay between these subjects. The purpose of the Workshop on Discrete Geometry, the Conference on Discrete Geometry and Optimization, and the Workshop on Optimization, held in September 2011 at the Fields Institute, Toronto, was to further stimulate the interaction between geometers and optimizers. This volume reflects the interplay between these areas.

The inspiring Fejes Toth Lecture Series, delivered by Thomas Hales of the University of Pittsburgh, exemplified this approach. While these fields have recently witnessed a lot of activity and successes, many questions remain open. For example, Fields medalist Stephen Smale stated that the question of the existence of a strongly polynomial time algorithm for linear optimization is one of the most important unsolved problems at the beginning of the 21st century. The broad range of topics covered in this volume demonstrates the many recent and fruitful connections between different approaches, and features novel results and state-of-the-art surveys as well as open problems.

Content:
Front Matter....Pages i-x
Discrete Geometry in Minkowski Spaces....Pages 1-15
Engineering Branch-and-Cut Algorithms for the Equicut Problem....Pages 17-32
An Approach to the Dodecahedral Conjecture Based on Bounds for Spherical Codes....Pages 33-44
On Minimal Tilings with Convex Cells Each Containing a Unit Ball....Pages 45-54
On Volumes of Permutation Polytopes....Pages 55-77
Monotone Paths in Planar Convex Subdivisions and Polytopes....Pages 79-104
Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint....Pages 105-120
The Strong Dodecahedral Conjecture and Fejes Toth’s Conjecture on Sphere Packings with Kissing Number Twelve....Pages 121-132
Solving Nuclear Norm Regularized and Semidefinite Matrix Least Squares Problems with Linear Equality Constraints....Pages 133-162
Techniques for Submodular Maximization....Pages 163-177
A Further Generalization of the Colourful Caratheodory Theorem....Pages 179-190
Expected Crossing Numbers....Pages 191-211
EL-Labelings and Canonical Spanning Trees for Subword Complexes....Pages 213-248
Bandwidth, Vertex Separators, and Eigenvalue Optimization....Pages 249-263
Exploiting Symmetries in Polyhedral Computations....Pages 265-278
Conditions for Correct Sensor Network Localization Using SDP Relaxation....Pages 279-301
A Primal–Dual Smooth Perceptron–von Neumann Algorithm....Pages 303-320
Selected Open Problems in Discrete Geometry and Optimization....Pages 321-336

---

??Optimization has long been a source of both inspiration and applications for geometers, and conversely, discrete and convex geometry have provided the foundations for many optimization techniques, leading to a rich interplay between these subjects. The purpose of the Workshop on Discrete Geometry, the Conference on Discrete Geometry and Optimization, and the Workshop on Optimization, held in September 2011 at the Fields Institute, Toronto, was to further stimulate the interaction between geometers and optimizers. This volume reflects the interplay between these areas.

The inspiring Fejes Toth Lecture Series, delivered by Thomas Hales of the University of Pittsburgh, exemplified this approach. While these fields have recently witnessed a lot of activity and successes, many questions remain open. For example, Fields medalist Stephen Smale stated that the question of the existence of a strongly polynomial time algorithm for linear optimization is one of the most important unsolved problems at the beginning of the 21st century. The broad range of topics covered in this volume demonstrates the many recent and fruitful connections between different approaches, and features novel results and state-of-the-art surveys as well as open problems.

Content:
Front Matter....Pages i-x
Discrete Geometry in Minkowski Spaces....Pages 1-15
Engineering Branch-and-Cut Algorithms for the Equicut Problem....Pages 17-32
An Approach to the Dodecahedral Conjecture Based on Bounds for Spherical Codes....Pages 33-44
On Minimal Tilings with Convex Cells Each Containing a Unit Ball....Pages 45-54
On Volumes of Permutation Polytopes....Pages 55-77
Monotone Paths in Planar Convex Subdivisions and Polytopes....Pages 79-104
Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint....Pages 105-120
The Strong Dodecahedral Conjecture and Fejes Toth’s Conjecture on Sphere Packings with Kissing Number Twelve....Pages 121-132
Solving Nuclear Norm Regularized and Semidefinite Matrix Least Squares Problems with Linear Equality Constraints....Pages 133-162
Techniques for Submodular Maximization....Pages 163-177
A Further Generalization of the Colourful Caratheodory Theorem....Pages 179-190
Expected Crossing Numbers....Pages 191-211
EL-Labelings and Canonical Spanning Trees for Subword Complexes....Pages 213-248
Bandwidth, Vertex Separators, and Eigenvalue Optimization....Pages 249-263
Exploiting Symmetries in Polyhedral Computations....Pages 265-278
Conditions for Correct Sensor Network Localization Using SDP Relaxation....Pages 279-301
A Primal–Dual Smooth Perceptron–von Neumann Algorithm....Pages 303-320
Selected Open Problems in Discrete Geometry and Optimization....Pages 321-336
....