7.3 Research Guidance

7.3.1 The Multiple Set Orienteering Problem
My Ph.D. student, Ravi Kant, is working on the Multiple Set Orienteering Problem [14, 15, 16, 17]. Set Orienteering Problem is a generalization of the Orienteering Problem where customers are grouped in clusters and a profit is associated with each cluster. The profit of a cluster is collected only if at least one customer from the cluster is visited. A single salesman is available to collect the profit and the objective is to find the salesman route that maximizes the profit collected and such that the route duration does not exceed a given threshold. We are proposing the Multiple Set Orienteering Problem [14, 15, 16, 17] in which
there are multiple salesmen, and we are designing algorithms for solving this problem.

7.3.2 Structural and Spectral Properties of Corona Graphs
My Ph.D. student (joint supervision with Dr. Bibhas Adhikari), Rohan Sharma, has done work on the structural and spectral properties of corona graphs [20, 3]. Given a small simple connected graph which we call seed graph, corona graphs are defined by taking the corona product of the seed graph iteratively. We have shown that the cumulative degree distribution of corona graphs decay exponentially when the seed graph is regular and the cumulative betweenness distribution follows power law when the seed graph is a clique. We determined spectra and signless Laplacian spectra of corona graphs in terms of the corresponding spectra of the seed graph when the seed graph is regular or a complete bipartite graph. Laplacian spectra of corona graphs corresponding to any seed graph are obtained in terms of the Laplacian spectra of the seed graph.

7.3.3 Contention-Aware Task Scheduling Algorithms

My B.E. student, Prasoon Trivedi, has done work on contention-aware task scheduling algorithms [2]. We considered the contention-aware task scheduling problem on a grid topology of processors. By contention-awareness, we mean that simultaneous communication on a link has to be serialized. To solve this problem, we proposed several nature-inspired metaheuristic algorithms: Simulated Annealing, Genetic Algorithm, Differential Evolution, Particle Swarm Optimization, Bat Algorithm, Cuckoo Search, and Firefly Algorithm. We performed benchmark evaluation of these algorithms for the Normalized Schedule Length parameter. The benchmark task graphs that we considered were: random task graphs, peer set task graphs, systolic array task graphs, Gaussian elimination task graphs, divide and conquer task graphs, and fast Fourier transform task graphs.

7.3.4 Simulated Annealing Based Energy-Efficient Task Scheduling Algorithm for Multi-Core Processors
My B.E. student, Pratik Satish, has done work on Simulated Annealing based energy-efficient task scheduling algorithm for multi-core processors [18]. We proposed a Simulated Annealing based energy-efficient task scheduling algorithm for multi-core processors and compared it with the EETSA algorithm [7]. Our results showed up to 26.97% improvement over the EETSA algorithm [7].