Optimization seminar

Modal title

Modal content

Datum / Zeit

Referent:in

Titel

Ort

8. Mai 2017
16:30-17:30

Dr. Alfonso Cevallos Manzano
ETH Zurich, Switzerland

Details

Titel	A PTAS for the max-sum dispersion problem in constant dimension.
Referent:in, Affiliation	Dr. Alfonso Cevallos Manzano, ETH Zurich, Switzerland
Datum, Zeit	8. Mai 2017, 16:30-17:30
Ort	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. Mai 2017
16:30-17:30

Dr. Joseph Paat
ETH Zurich, Switzerland

Details

Titel	Approximation of corner polyhedron with families of intersection cuts
Referent:in, Affiliation	Dr. Joseph Paat, ETH Zurich, Switzerland
Datum, Zeit	15. Mai 2017, 16:30-17:30
Ort	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. Mai 2017
16:30-17:30

Dr. Andrea Baggio
ETH Zurich, Switzerland

Details

Titel	Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center
Referent:in, Affiliation	Dr. Andrea Baggio, ETH Zurich, Switzerland
Datum, Zeit	22. Mai 2017, 16:30-17:30
Ort	HG G 19.1

Efficient Infrastructure Planning and Room Scheduling for a New Surgery Center

29. Mai 2017
16:30-17:30

Dr. Christos Kalaitzis
ETH Zurich, Switzerland

Details

Titel	Scheduling jobs with uniform Smith ratios to minimize the weighted sum of completion times
Referent:in, Affiliation	Dr. Christos Kalaitzis, ETH Zurich, Switzerland
Datum, Zeit	29. Mai 2017, 16:30-17:30
Ort	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

Hinweise: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archiv: FS 22 FS 20 HS 19 FS 19 HS 18 FS 18 HS 17 FS 17 HS 16 FS 16 HS 15 FS 15 HS 14 FS 14 HS 13 FS 13 HS 12 FS 12 HS 11 FS 11 HS 10 FS 10 HS 09