MPI-INF Logo
Campus Event Calendar

Event Entry

New for: D1, D2, D3, D4, D5

What and Who

A Simple Solution for the Min-Max Selecting Items Problem

Benjamin Doerr
Max-Planck-Institut für Informatik - D1
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Friday, 19 April 2013
13:00
30 Minutes
E1 4
024
Saarbrücken

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

Benjamin Doerr
--email hidden
passcode not visible
logged in users only

Benjamin Doerr, 04/19/2013 08:53
Benjamin Doerr, 04/18/2013 07:09
Benjamin Doerr, 04/17/2013 20:04
Benjamin Doerr, 04/17/2013 20:02 -- Created document.