Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Tight Lower Bound for Online Convex Optimization with Switching Costs
Speaker:Kevin Schewior
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 19 October 2017
Duration:30 Minutes
Building:E1 4

We investigate online convex optimization with switching costs (OCO; Lin et al., INFOCOM 2011), a natural online problem arising when rightsizing data centers: A server initially located at p_0 on the real line is presented with an online sequence of non-negative convex functions f_1, f_2, ..., f_n: R -> R_+. In response to each function f_i, the server moves to a new position p_i on the real line, resulting in cost |p_i-p_{i-1}|+f_i(p_i). The total cost is the sum of costs of all steps. One is interested in designing competitive algorithms.

In this paper, we solve the problem in the classical sense: We give a lower bound of 2 on the competitive ratio of any possibly randomized online algorithm, matching the competitive ratio of previously known deterministic online algorithms (Andrew et al., COLT 2013/arXiv 2015; Bansal et al., APPROX 2015). It was previously conjectured that (2-eps)-competitive algorithms exist for some eps>0 (Bansal et al., APPROX 2015).

This is joint work with Antonios Antoniadis and was presented at WAOA 2017.

Name(s):Kevin Schewior
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Antonios Antoniadis, 10/04/2017 02:39 PM Last modified:Uwe Brahm/MPII/DE, 10/19/2017 07:00 AM
  • Kevin Schewior, 10/04/2017 08:03 PM
  • Antonios Antoniadis, 10/04/2017 02:40 PM
  • Antonios Antoniadis, 10/04/2017 02:39 PM -- Created document.