# Optimization and applications seminar

## Spring Semester 2017

Note: The highlighted event marks the next occurring event.

Date / Time Speaker Title Location
17 April 2017
16:30-17:30
No Event (Easter Holiday) HG G 19.1
24 April 2017
16:30-17:30
No Event (Sechseläuten) HG G 19.1
1 May 2017
16:30-17:30
No Event (Labour Day) HG G 19.1
8 May 2017
16:30-17:30
Dr. Alfonso Cevallos Manzano
ETH Zurich, Switzerland
HG G 19.2
Abstract: Given n points in Euclidean space, and a number k, the max-sum dispersion problem asks to find a subset of size k with maximum average pairwise distance. This is a classical diversity problem with applications in the location of facilities that need to be "spread out", as well as applications with large databases whenever we need a small and diverse sample. I will present a PTAS for the problem, for instances with bounded doubling dimension. The latter is a very broad notion of dimension on general metric spaces. In particular, the result implies a PTAS for distances induced by any L_p norm of bounded dimension, for any p.
15 May 2017
16:30-17:30
Dr. Joseph Paat
ETH Zurich, Switzerland
HG G 19.1
Abstract: The corner polyhedron is a relaxation of a mixed-integer linear set. One advantage of using the corner polyhedron as a relaxation is that it can be described by so-called intersection cuts, which are valid inequalities derived from lattice-free polyhedra. However, classifying lattice-free sets has proven to be quite difficult, so accessing the complete list of intersection cuts seems unlikely. Here we develop conditions for a family of intersection cuts to closely approximate the corner polyhedron. We characterize "strong" approximations based upon the number of facets of the underlying lattice-free polyhedra. This work was with Gennadiy Averkov from the University of Magdeburg and Amitabh Basu from Johns Hopkins University.
22 May 2017
16:30-17:30
Dr. Andrea Baggio
ETH Zurich, Switzerland
Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center HG G 19.1
29 May 2017
16:30-17:30
Dr. Christos Kalaitzis
ETH Zurich, Switzerland
HG G 19.1
Abstract: We consider the problem of scheduling jobs on unrelated machines in order to minimize the weighted sum of completion times. For this problem, the best known approximation guarantee is $3/2-\epsilon$, for some small $\epsilon$, due to Bansal et al. In this talk, we will focus on the specific case of the problem, where the involved jobs have uniform weight/size ratios (also known as Smith ratios). For this restricted version of the problem, we show how to achieve an approximation guarantee of 1.21. We do this by providing a randomized rounding scheme, which rounds solutions to the Configuration-LP relaxation of the problem. Our main technical contribution is analyzing this rounding scheme, by comparing the cost of the output distribution of this randomized rounding to the cost of a specific class of worst-case output distributions. This is joint work with Ola Svensson and Jakub Tarnawski.​

Page URL: https://www.math.ethz.ch/news-and-events/events/research-seminars/optimization-applications-seminar.html
Wed Jun 28 08:22:30 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich