[Talks@IDSIA] PIDSIA Seminar by Seeun William Umboh, 10th July

Speaker: Seeun William Umboh Title: Nested Convex Bodies are Chaseable Abstract: In the Convex Body Chasing problem, we are given an initial point v_0 in R^d and an online sequence of n convex bodies F_1 , … , F_n. When we receive F_i, we are required to move inside F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt{d}) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. We consider the setting in which the convex bodies are nested: F_i contains F_{i+1}. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial's conjecture. In this work, we give the first f(d)-competitive algorithm for chasing nested convex bodies in R^d. Bio: William Umboh is a Lecturer in Algorithms at the University of Sydney. He received his Ph.D. from the University of Wisconsin-Madison in 2015 and subsequently was a postdoc at the Eindhoven University of Technology during 2015-2018. His main research interest is in designing approximation algorithms and online algorithms for combinatorial optimization problems. When: Tuesday 10th of July 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: Pizza (or alternative food) and drinks will be offered at the end of the talk. If you plan to attend, please register in a timely fashion at the following link so that we will have no shortage of food: https://doodle.com/poll/5y8d232ykqsdcwus