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
No Event (Easter Holiday) HG G 19.1 
24 April 2017
No Event (Sechseläuten) HG G 19.1 
1 May 2017
No Event (Labour Day) HG G 19.1 
8 May 2017
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
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
Dr. Andrea Baggio
ETH Zurich, Switzerland
Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center HG G 19.1 
29 May 2017
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