Optimization and applications seminar

Main content

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
A PTAS for the max-sum dispersion problem in constant dimension.   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
Approximation of corner polyhedron with families of intersection cuts  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
Scheduling jobs with uniform Smith ratios to minimize the weighted sum of completion times  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.​

Archive: AS 17  SS 17  AS 16  SS 16  AS 15  SS 15  AS 14  SS 14  AS 13  SS 13  AS 12  SS 12  AS 11  SS 11  AS 10  SS 10  AS 09 

 
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