Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Dynamicity and Multi-commodity in Networks
event speaker icon
Yaron Fairstein (Ph.D. Thesis Seminar)
event date icon
Sunday, 12.09.2021, 15:00
event location icon
Zoom Lecture: 93358148665
event speaker icon
Advisor: Prof. J. Naor and Prof. D. Raz
The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this talk we will consider the multistage extension of two optimization problems, Facility Location and Multiple Knapsack. A constant approximation factor is presented for Multistage Facility Location, and a PTAS for Generalized Multistage $d$-Knapsack.