D-MATH Weekly BulletinNews and Events (in particular 'Research Seminars') at D-MATH, ETH Zurichen-us
http://www.fim.math.ethz.ch/bulletin
Wed, 24 Aug 2016 08:23:07 +020060Michel Goemans - Newton's Method and Separable Convex Minimization over Submodular Polyhedra<h2 color="grey">Conference: Discrete Optimization</h2><h1>Newton's Method and Separable Convex Minimization over Submodular Polyhedra</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Michel Goemans, Massachusetts Institute of Technology<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 24 August 2016 @ 09:30<br /><br /><strong>Abstract:</strong><br />We present two results on submodular polyhedra. We first give the first strongly polynomial bound on the number of iterations of Newton's method for the line search problem for an arbitrary (not necessarily nonnegative) direction over a submodular polyhedron. This generalizes results of Radzik for Newton's method for linear fractional combinatorial optimization. We also present a conceptually simple algorithm for minimizing a separable convex function over a submodular base polytope. We discuss its efficiency depending on the convex function and the structure of the submodular function.<br /><br />This is joint work with Swati Gupta and Patrick Jaillet.http://www.math.ethz.ch/screen/info?guid=9188Fri, 19 Aug 2016 12:05:19 +0200András Sebő - The Salesman's Matroid Intersections<h2 color="grey">Conference: Discrete Optimization</h2><h1>The Salesman's Matroid Intersections</h1><br /><font color="grey">Speaker:</font> Prof. Dr. András Sebő, Université Grenoble Alpes<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 24 August 2016 @ 10:45<br /><br /><strong>Abstract:</strong><br />In various recent results about the Travelling Salesman's problem or its variants (for graph metrics in a joint work with Jens Vygen, for paths in a joint work with Anke van Zuylen, for k-trails in a work of Singh and Zenklusen, or for a hypergraph generalization of the Hamiltonian cycle feasibility problem by Jeno Lehel) Edmonds' matroid intersection or partition theorems are helpful to use. <br /><br />Are matroids inherent in these problems? Are its apparently independent occurrences in fact related? Do their occurrences have a common reason? <br /><br />We cannot answer these questions but show some of the Salesman's travelling experiences on intersecting roads of connectivity, parity and matroids. We show some common features of the mentioned problems, and some open questions they are leading to. http://www.math.ethz.ch/screen/info?guid=9189Mon, 15 Aug 2016 10:50:17 +0200Friedrich Eisenbrand - title t.b.a.<h2 color="grey">Conference: Discrete Optimization</h2><h1>title t.b.a.</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Friedrich Eisenbrand, EPF Lausanne<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 24 August 2016 @ 11:30http://www.math.ethz.ch/screen/info?guid=9184Sun, 21 Aug 2016 13:59:40 +0200Bruce Shepherd - Trees, Flows, and Clusters<h2 color="grey">Conference: Discrete Optimization</h2><h1>Trees, Flows, and Clusters</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Bruce Shepherd, McGill University<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 09:30<br /><br /><strong>Abstract:</strong><br />Tree structures have appeared persistently both in the models and algorithms for combinatorial optimization. Not surprisingly, there is an associated well-developed toolkit for these problems. It is perhaps surprising that the classical model of flows in networks (aka Max-flow Min-cut) admits several natural open questions when the flows must be routed on a tree: so-called confluent flows. We discuss a solution for one of those questions and explain connections to IP routing, rooted clustering and stable matchings.<br /><br />Coauthors: Adrian Vetta (McGill), Gordon Wilfong (Bell Labs)http://www.math.ethz.ch/screen/info?guid=9191Thu, 18 Aug 2016 13:20:52 +0200Ola Svensson - Lift-and-Round to Improve Scheduling on Unrelated Machines<h2 color="grey">Conference: Discrete Optimization</h2><h1>Lift-and-Round to Improve Scheduling on Unrelated Machines</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Ola Svensson, EPF Lausanne<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 10:45http://www.math.ethz.ch/screen/info?guid=9192Tue, 23 Aug 2016 15:15:31 +0200Neil Olver - A faster and simpler strongly polynomial algorithm for generalized flow maximization<h2 color="grey">Conference: Discrete Optimization</h2><h1>A faster and simpler strongly polynomial algorithm for generalized flow maximization</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Neil Olver, Vrije Universiteit Amsterdam<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 11:30<br /><br /><strong>Abstract:</strong><br />The maximum generalized flow problem, a classical generalization of maximum flow where flow is scaled as it traverses each arc, has been intensively studied for the past few decades. Only recently did Végh obtain a strongly polynomial time algorithm for it. We give a new strongly polynomial algorithm that is both substantially faster and dramatically simpler than the algorithm of Végh. It is in many cases slightly faster than even the best weakly polynomial algorithm due to Radzik. We also demonstrate an important application of our result to the classical net present value problem in project scheduling.<br /><br />(Joint work with J. Correa, A. Schulz and L. Végh.)http://www.math.ethz.ch/screen/info?guid=9193Thu, 18 Aug 2016 13:23:41 +0200Santanu Dey - Aggregation-based cutting-planes for packing and covering integer programs<h2 color="grey">Conference: Discrete Optimization</h2><h1>Aggregation-based cutting-planes for packing and covering integer programs</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Santanu Dey, Georgia Institute of Technology<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 14:00<br /><br /><strong>Abstract:</strong><br />We study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first main result is to show that for packing and covering IPs, the CG and aggregation closures can be 2-approximated by simply generating the respective closures for each of the original formulation constraints, without using any aggregations. On the other hand, we use computational experiments to show that aggregation cuts can be arbitrarily stronger than cuts from individual constraints for general IPs. Finally, we examine the strength of cuts based on k different aggregation inequalities simultaneously, the so-called multi-row cuts, and show that every packing or covering IP with a large integrality gap also has a large k-aggregation closure rank. In particular, this rank is always at least of the order of the logarithm of the integrality gap.<br />　<br />This is joint work with Merve Bodur, Alberto Del Pia, Marco Molinaro and Sebastian Pokuttahttp://www.math.ethz.ch/screen/info?guid=9194Thu, 18 Aug 2016 13:24:08 +0200Franziska Borer - Weak Solutions for the Ricci Flow on Closed Surfaces and Prescribed Curvature Problems<h2 color="grey">Doctoral Exam</h2><h1>Weak Solutions for the Ricci Flow on Closed Surfaces and Prescribed Curvature Problems</h1><br /><font color="grey">Speaker:</font> Franziska Borer, Examiner: Prof. Dr. Michael Struwe<br /><font color="grey">Location:</font> HG G 19.2 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 14:00http://www.math.ethz.ch/screen/info?guid=9138Tue, 02 Aug 2016 10:24:25 +0200Daniel Dadush - Making Banaszczyk's Bound Constructive for the Komlos Problem<h2 color="grey">Conference: Discrete Optimization</h2><h1>Making Banaszczyk's Bound Constructive for the Komlos Problem</h1><br /><font color="grey">Speaker:</font> Dr. Daniel Dadush, Centrum Wiskunde & Informatica<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 14:45<br /><br /><strong>Abstract:</strong><br />We first consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((tlogn)1/2), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t1/2logn) bound. The result also extends to the more general Komlos setting, where each vector has norm at most 1, and gives an algorithmic O(log1/2n) bound.<br /><br />Joint work with Nikhil Bansal and Shashwat Garg.http://www.math.ethz.ch/screen/info?guid=9195Thu, 18 Aug 2016 13:24:42 +0200Jesús de Loera - On the Foundations of Linear Optimization: two recent advances<h2 color="grey">Conference: Discrete Optimization</h2><h1>On the Foundations of Linear Optimization: two recent advances</h1><br /><font color="grey">Speaker:</font> Prof. Dr. Jesús de Loera, University of California, Davis<br /><font color="grey">Location:</font> HG G 19.1 (ETH Zentrum)<br /><font color="grey">Start Date/Time:</font> 25 August 2016 @ 16:00<br /><br /><strong>Abstract:</strong><br />Linear programs (LPs) and their associated polyhedra are, without any doubt, at the core of both the theory and the practice of Mathematical Optimization (in discrete optimization LPs are used in practical computations, e.g., branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). Despite their key importance, many simple easy-to-state mathematical questions about LPs remain wide open. At the same time, new applications in big data have raised new algorithmic questions we need to push forward. In this talk I will sketch two recent contributions to this region of Mathematical optimization:<br /><br />First, the open question of whether there exist a version of the simplex method that runs polynomial-time motivates the well-known geometric challenge of determining a worst-case upper bound for the diameter of polyhedra. Although a lot of progress has been made, today even for the most elementary textbook linear programs we remain ignorant as to what the exact diameter upper bounds are. I will present the key ideas for finally proving that the diameter of graphs of network-flow polytopes satisfy the Hirsch linear bound (joint work with S. Borgwardt and E. Finhold).<br /><br />Second, motivated by challenges in big data analytics, I will discuss iterative-projection algorithms for solving (very) large-scale systems of linear inequalities (think of systems that cannot be read entirely in memory or that constraints can only be sampled). We generalized the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method and show this new abstraction has attractive theoretical convergence results. Our computational experiments show our algorithms outperform the original iterative methods (joint work with J. Haddock and D. Needell).http://www.math.ethz.ch/screen/info?guid=9196Thu, 18 Aug 2016 13:25:03 +0200