D-MATH Weekly BulletinNews and Events (in particular 'Research Seminars') at D-MATH, ETH Zurichen-us
http://www.fim.math.ethz.ch/bulletin
Sun, 26 Apr 2015 22:54:14 +020060José Burgos Gill - The singularities of the invariant metric of the sheaf of Jacobi forms on the universal elliptic curve<h2 color="grey">Advanced Seminar in Algebraic Geometry (uzh)</h2><h1>The singularities of the invariant metric of the sheaf of Jacobi forms on the universal elliptic curve</h1><br /><font color="grey">Speaker:</font> Prof. Dr. José Burgos Gill, ICMAT<br /><font color="grey">Location:</font> Y27 H 25 (UZH Irchel)<br /><font color="grey">Start Date/Time:</font> 27 April 2015 @ 13:15http://www.math.ethz.ch/screen/info?guid=6506Mon, 20 Apr 2015 11:00:12 +0200Yurii Nesterov - Complexity and Simplicity of Optimization Problems<h2 color="grey">Nachdiplomvorlesung</h2><h1>Complexity and Simplicity of Optimization Problems</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Yurii Nesterov, Université catholique de Louvain (UCL)<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 27 April 2015 @ 14:15<br /><br /><strong>Abstract:</strong><br />In this course, we address a wide spectrum of questions related to theoretical justification of optimization algorithms and complexity of optimization problems. We start from comparing the mathematical and engineering paradigms, related to the concepts of problem instances, their importance and complexity. Computational Mathematics, and Optimization as its essential part, inherits somehow both alternative approaches. In particular, we discuss different definitions of the input data size and their consequences for our abilities to construct efficient optimization schemes. In the next lectures of the course, we look at intrinsic complexity of Black-Box Nonlinear Optimization, resulted in the lower complexity bounds and optimal first-order schemes. We also present new second-order methods, provided with the global efficiency estimates. After that, we discuss different approaches of Structural Optimization, which lead to significant acceleration of Black-Box minimization schemes. Next topics are optimization in relative scale and huge-scale optimization problems. Last lectures of the course are devoted to some applications (nonlinear analysis of combinatorial problems and algorithmic models of human behavior).http://www.math.ethz.ch/screen/info?guid=6645?27 April 2015Tue, 03 Feb 2015 14:12:40 +0100Kathrin Näf - On the existence of infinitely many invariant Reeb orbits<h2 color="grey">Symplectic Geometry Seminar</h2><h1>On the existence of infinitely many invariant Reeb orbits</h1><br /><font color="grey">Speaker:</font> Kathrin Näf, ETH Zürich<br /><font color="grey">Location:</font> HG G 43 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 27 April 2015 @ 15:15http://www.math.ethz.ch/screen/info?guid=6854Tue, 21 Apr 2015 10:31:54 +0200Jens Vygen - Reassembling Trees for the Traveling Salesman<h2 color="grey">Optimization and Applications Seminar</h2><h1>Reassembling Trees for the Traveling Salesman</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Jens Vygen, Universität Bonn<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 27 April 2015 @ 16:30<br /><br /><strong>Abstract:</strong><br />Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm).<br />We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions.<br />We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebő’s previously best approximation ratio of 8/5.http://www.math.ethz.ch/screen/info?guid=5071Tue, 21 Apr 2015 10:32:22 +0200