Campus Event Calendar: Antonios Antoniadis (09/02/2014 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line

Antonios Antoniadis

Max-Planck-Institut für Informatik - D1

AG1 Mittagsseminar (own work)

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Tuesday, 2 September 2014

13:00

30 Minutes

E1 4

024

Saarbrücken

Abstract

Online matching on a line involves matching an online stream of items of various sizes to stored items of various sizes, with the objective of minimizing the average discrepancy in size between matched items. The best previously known upper and lower bounds on the optimal deterministic competitive ratio are linear in the number of items, and constant, respectively. We show that online matching on a line is essentially equivalent to a particular search problem, that we call k-lost cows. We then obtain the first deterministic sub-linearly competitive algorithm for online matching on a line by giving such an algorithm for the k-lost cows problem.

Contact

Antonios Antoniadis

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Antonios Antoniadis, 08/19/2014 10:54 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis