CS Seminar: On the Complexity of Various Reload/Changeover Cost Problems12-02-2020

Speaker: Mordohay Shalom, Technion

Title: On the Complexity of Various Reload/Changeover Cost Problems

Date/Time: 13 February, 2020  /  11.40-12.30

Place: FENS L063

Abstract: The reload and changeover cost concepts refer to the cost that occurs at a vertex along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. These costs depends only on the colors of the traversed edges. They appear in various applications such as transportation networks, energy distribution networks, and telecommunications. Previous work on focuses on several problems such as finding a minimum spanning tree, a minimum diameter spanning tree, a minimum cost cycle covering. All these problems were known to be NP-complete in their most general form. However, a little was known regarding their approximability and parameterized complexity. In a series of works we analyzed the problems from these perspectives and we were able to provide a more fine-grained picture of the complexity of these problems, with hardness results from one side and approximation/FPT algorithms from the other.

Bio: Mordohay Salom, holds a B.A. degree in Architecture from ITU, Techni- cal University of Istanbul, from which he graduated at 1981. He received his Ph.D. degree from the Faculty of Computer Science, Technion, at 2006. Since then he serves as Senior Lecturer in the Tel Hai Academic college and as Adjunct Lecturer at the Technion. His research interests are Optimiza- tion Problems in Optical Networks, Distributed Algorithms, Approximation Algorithms, Online Algorithms, Algorithmic Graph Theory.

Contact: Öznur Taştan