Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Gastvortrag Prof. Dr. Meyer auf der Heide

  • Wann 13.02.2017 von 14:15 bis 23:59
  • Wo RUD 25, Humboldt-Kabinett
  • iCal

Herr Prof. Dr. Friedhelm Meyer auf der Heide (Univ. Paderborn) wird bei uns zu Gast sein und einen Vortrag zum Thema "Online Resource Leasing" halten.
Alle Interessenten sind herzlich eingeladen!


Decisions regarding which resources to acquire in order to provide services comprise the core of many optimization problems. Classical problems which fall into this category of problems are for example Facility Location, Steiner Tree, and Set Cover, as well as several scheduling problems. Such problems have been widely studied in both offline and online settings. Traditionally, the decisions are considered to be final: we buy the resources. Once a resource is bought, it can be used any time in the future without inducing further costs.
Inspired by the Cloud Computing market, we consider the leasing variants of the above problems: Resources are not bought, but leased for a given time interval; the cost for a lease typically grows with the length of the interval, but the cost per time unit decreases with this length.
Such a model for leasing was introduced by Meyerson as the parking permit problem. In the talk, I will present online algorithms for several resource leasing problems. Technically, our algorithmic approach is mostly based on an online variant of primal-dual approximation algorithms.
The talk presents joint work with Christine Markarian.