Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1, D2, D3, D4, D5
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Simple Solution for the Min-Max Selecting Items Problem
Speaker:Benjamin Doerr
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 19 April 2013
Duration:30 Minutes
Building:E1 4
We give a simple O(log K / loglog K) approximation algorithm for the min-max selecting items problem. Since this number is the integrality gap of the LP formulation by Kasperski and Zieli\'nski (Annals OR (2009)), it is unlikely that LP-based methods can lead to better results. If time permits, I will also show how to make the approximation algorithm run in the RAM model of computation, that is, avoiding the assumption that rational powers of integers can be computed with arbitrary precision in constant time.
Name(s):Benjamin Doerr
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Benjamin Doerr, 04/19/2013 08:53 AM
  • Benjamin Doerr, 04/18/2013 07:09 AM
  • Benjamin Doerr, 04/17/2013 08:04 PM
  • Benjamin Doerr, 04/17/2013 08:02 PM -- Created document.