Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Friday, 19 April 2013
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Benjamin Doerr
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
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.