MPI-INF Logo
Campus Event Calendar
  • Home
  • Campus Event Calendar

Event Entry

What and Who

Learning-Augmented Online Selection Algorithms

Pieter Kleer
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 7 April 2020
13:00
30 Minutes
Video only
000
Saarbrücken

Abstract

We study online selection problems in which the goal is to select a set of elements arriving online that maximize a given objective function. In our setting, we are given some (machine-learned) information regarding the optimal (offline) solution to the problem. Following a recent line of work, the goal is to incorporate this information in existing (constant-factor) approximation algorithms such that:

i) One gets an improved approximation guarantee in case the machine-learned information is accurate;
ii) One does not lose too much in the approximation guarantee of the original algorithm in case the information is highly inaccurate.

In this talk, I will illustrate these concepts using the classical secretary problem, and discuss some extensions to other online selection problems such as online bipartite matching.

--------------------------
Join Zoom Meeting
https://zoom.us/j/5272788807?pwd=bmFVaUMyeURYNDJLT2kyaWVQNEdiUT09

Meeting ID: 527 278 8807
For people outside D1, please email skisfalu@mpi-inf.mpg.de if you wish to join.

Contact

Sándor Kisfaludi-Bak
--email hidden
passcode not visible
logged in users only
Login for more details

Tags, Category, Keywords and additional notes

Join Zoom Meeting
https://zoom.us/j/5272788807?pwd=bmFVaUMyeURYNDJLT2kyaWVQNEdiUT09
Meeting ID: 527 278 8807

For people outside D1, please email skisfalu@mpi-inf.mpg.de if you wish to join

Sándor Kisfaludi-Bak, 04/06/2020 11:31
Sándor Kisfaludi-Bak, 03/31/2020 14:26
Sándor Kisfaludi-Bak, 03/30/2020 13:54
Sándor Kisfaludi-Bak, 03/30/2020 13:50 -- Created document.