on Wednesday, April 26, 2023, at 10 a.m. in heiconf: https://audimax.heiconf.uni-heidelberg.de/nnry-r3pk-3e2m-vayw
If you like dynamic programming, then this talk is for you.
Abstract:
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity.
In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1+ε)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. Our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. We further present several applications of our result. For a bicriteria version of k-balanced graph partitioning, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.
This is joint work with Monika Henzinger, Harald Räcke and Stefan Schmid. The full version of the paper can be found on arxiv https://arxiv.org/abs/2301.01744 <https://arxiv.org/abs/2301.01744>
Stefan Neumann is currently an assistant professor at KTH Royal Institute of Technology in Stockholm, Sweden. His research primarily revolves around the development of practical data science algorithms that come with provable guarantees. Stefan has a record of publications in leading computer science conferences, such as ICML, NeurIPS, and the WebConf. He completed his Ph.D. in 2020 at the University of Vienna, where he was supervised by Monika Henzinger. His Ph.D. thesis has been awarded the Heinz Zemanek Award from the Austrian Computer Society and an Award of Excellence from the Austrian Federal Government.
