- אירוע כבר עבר.
On the Parameterized Tractability of Machine Scheduling Problems
מאי 7, 2019 @ 12:00 pm - 1:00 pm
Parameterized complexity facilitates the analysis of computational problems in terms of various instance parameters that may be independent of the total input length. This area has enjoyed tremendous success since its first developments in the early 90s, contributing many new techniques to the area of algorithmic design. However, one field that has been very much neglected by the researchers in the parameterized complexity community is the area of scheduling. This is rather disappointing considering that (i) scheduling is one of the most classical areas of combinatorial optimization, with several important problems that direct real-life applications, and that (ii) typical scheduling problems have many natural parameters associated with them that can be relatively small in practice compared to the total instance length. Our goal is to bridge this gap by analyzing various scheduling problems through the parameterized complexity lens by considering common scheduling parameters such as the number of di¤erent processing times, due-dates, and weights.
Dvir Shabtay completed his Ph.D. studies in 2003 at the Department of Industrial Engineering and Management at Ben-Gurion University of the Negev (BGU), and since then serves as a faculty member at the department. He received a full professor rank in 2016 and is currently the chair of Sir John and Lady Cohen cathedra in Business and Industrial Management. He also serves as the head of the teaching committee of the engineering faculty at BGU.
Dvir’s research focuses on the analysis of several aspects of scheduling problems, including computational classification, parameterized complexity, approximation, and online algorithms. He also analyzes other combinatorial optimization problems including various extensions and special cases of network/graph problems.
Dvir published since 2003 more than 60 papers in various journals including Omega, Discrete Applied Mathematics, Journal of scheduling, MSOM, European Journal of Operations Research, Computers and Operations Research, IIE Transactions and Journal of Combinatorial Optimization. He also serves as an associate editor for Journal of Scheduling and European Journal of Operations Research and as an external advisor for the bank of Israel.