Title: Two heuristics for the rainbow spanning forest problem
Speaker: Dr. Sudishna Ghoshal
Venue: IEOR Seminar Room
Date and time: 18 November 2024 (Monday), 10:00 AM - 11:00 AM
Abstract: A rainbow spanning forest (say RF) of a given connected, undirected and edge-colored graph (G) is a spanning forest of a set of rainbow components, where a rainbow component is a tree whose edges have different colors. The rainbow spanning forest problem (RSFP) of G aims to find a RF of G with the minimum number of rainbow components. The RSFP which is recently introduced is NP-hard on general graphs and trees, but finds its applications in many situations in which one requires to distinguish between different types of connections in network. To the best of our knowledge, there exists only one paper (Carrabs et al. 2018b) that presents a problem-specific heuristic called greedy algorithm (say GH) and a multi-start scheme embedding this GH (say MSGH) in order to further improve the results. This paper presents a novel and fast problem-specific heuristic Heu_RSF. With the intent of improving solution quality at the cost of higher computational time, we present an artificial bee colony algorithm (ABC_RSFP) for the RSFP. Main components of ABC_RSFP such as randomized version of Heu_RSF in solution initialization and grouping-based neighborhood strategies in conjunction with the use of Heu_RSF as a repair operator help in making ABC_RSFP more effective framework. On a set of benchmark instance scenarios, experimental results suggest that Heu_RSF is effective particularly on instances of larger scenarios with higher density and is computationally much faster than GH and MSGH. ABC_RSFP outperforms MSGH on almost all instance scenarios and shows its effectiveness in terms of computational time.
Biography: Dr. Sudishna Ghoshal is an Assistant Professor at TAPMI, Manipal Academy of Higher Education in Decision Sciences. Dr. Ghoshal earned her Ph.D. from the National Institute of Technology(NIT) Raipur. Sudishna gained postdoctoral experience at IIT Jodhpur. Her academic journey commenced at Guru Ghasidas Central University, where she excelled in computer science, graduating with distinction. Her Master's thesis on a One-Class Naive Bayes Classifier for Credit Card Dataset, conducted at the Indian Statistical Institute Kolkata, laid the groundwork for future research endeavors. Her research focuses on heuristic and metaheuristic approaches for NP-Hard Combinatorial Optimization Problems. She has co-authored several research items in peer-reviewed international journals such as the European Journal of Operations Research (EJOR), Applied Soft Computing, Journal of Retailing and Consumer Services, etc.