Optimization Seminar

Modal title

Modal content

Date / Time

Speaker

Title

Location

8 May 2017
16:30-17:30

Dr. Alfonso Cevallos Manzano
ETH Zurich, Switzerland

Event Details

Title	A PTAS for the max-sum dispersion problem in constant dimension.
Speaker, Affiliation	Dr. Alfonso Cevallos Manzano, ETH Zurich, Switzerland
Date, Time	8 May 2017, 16:30-17:30
Location	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.

A PTAS for the max-sum dispersion problem in constant dimension. read_more

15 May 2017
16:30-17:30

Dr. Joseph Paat
ETH Zurich, Switzerland

Event Details

Title	Approximation of corner polyhedron with families of intersection cuts
Speaker, Affiliation	Dr. Joseph Paat, ETH Zurich, Switzerland
Date, Time	15 May 2017, 16:30-17:30
Location	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.

Approximation of corner polyhedron with families of intersection cutsread_more

22 May 2017
16:30-17:30

Dr. Andrea Baggio
ETH Zurich, Switzerland

Event Details

Title	Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center
Speaker, Affiliation	Dr. Andrea Baggio, ETH Zurich, Switzerland
Date, Time	22 May 2017, 16:30-17:30
Location	HG G 19.1

Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center

29 May 2017
16:30-17:30

Dr. Christos Kalaitzis
ETH Zurich, Switzerland

Event Details

Title	Scheduling jobs with uniform Smith ratios to minimize the weighted sum of completion times
Speaker, Affiliation	Dr. Christos Kalaitzis, ETH Zurich, Switzerland
Date, Time	29 May 2017, 16:30-17:30
Location	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.

Scheduling jobs with uniform Smith ratios to minimize the weighted sum of completion timesread_more

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 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