Schedule: 18th Febuary, 3.30 pm
Place: GSSI Main Hall
Title: On the Complexity of Various Reload/Changeover Cost Problems
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 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.
Speaker: Prof. Mordo Shalom
Hit-Holon Institute of Technology
Israel
Hit-Holon Institute of Technology
Israel
On the Complexity of Various Reload/Changeover Cost Problems