Rishi Ranjan Singh
Assistant Professor
Dept. of Electrical Engineering and Computer Science
Indian Institute of Technology, Bhilai
E-mail: rishi@iitbhilai.ac.in
Areas of Interest
- Social & Complex Network Analysis, Approximation Algorithms, Combinatorial Optimization, Mathematical Formulation, Vehicle Routing Problems, Graph Theory, Theoretical computer science.
Education
- PhD, 2016, Indian Institute of Technology Ropar
- BTech, 2011, Uttar Pradesh Technical University, Lucknow, India
Teaching
- Theory of Computation
- Complexity Theory
- Approximation Algorithms
- Network Science
- Social and Complex Network Analysis
Experience
- August 2017-Present: Assistant Professor, Dept. of Computer Science and Engineering, IIT Bhilai, India.
- April 2016-August 2017: Assistant Professor, Dept. of Information Technology, IIIT Allahabad, India.
- September 2015-April 2016: Visiting Faculty, Dept. of Information Technology, IIIT Allahabad, India.
Selected Publications
-
Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. Amongst a plethora of application-specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the widely applied ones. We are surrounded by networks where information, signal or commodities are flowing through the edges. Betweenness centrality comes as a handy tool to analyze such systems, but computation of these scores is a daunting task in large-size networks. Since computing the betweenness centrality of one node is conjectured to be same as time taken for computing the betweenness centrality of all the nodes, a fast algorithm was required that can efficiently estimate a node’s betweenness score. In this paper, we propose a heuristic that efficiently estimates the betweenness score of a given node. The algorithm incorporates a non-uniform node-sampling model which is developed based on the analysis of random Erdős-Rényi graphs. We apply the heuristic to estimate the ranking of an arbitrary k vertices, called betweenness-ordering problem, where k is much less than the total number of vertices. The proposed heuristic produces very efficient results even when runs for a linear time in the number of edges. An extensive experimental evidence is presented to demonstrate the performance of the proposed heuristic for betweenness estimation and ordering on several synthetic and real-world graphs.
-
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max {1+ 1.5 α, 3} max {1+ 1. 5 α, 3} and 6, respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al.(2012) and Daya Ram Gaur et al.(2013). The bounds reported here improve the bounds in Daya Ram Gaur et al.(2016).
-
There has been a recent resurge of interest in vehicle routing problems, especially in the context of green vehicle routing. One popular and simplified model is that of the cumulative vehicle routing problem. In this chapter, we examine the motivation, the definition, and the mixed integer linear program for the cumulative VRP. We review some of the recent results on approximation algorithms for the cumulative VRP. A column generation-based procedure for solving the cumulative VRP is also described. We also review approximation algorithms for a stochastic version of the cumulative VRP.
-
Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we computationally study, an inexact approach for constructing solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation and is solved using column generation. The pricing subproblem is solved heuristically using dynamic programming. Simulation results show that a simple scalable strategy gives solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation.
-
In this paper we give randomized approximation algorithms for stochastic cumulative VRPs for split and unsplit deliveries. The approximation ratios are 2(1+α) and 7 respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. These results extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].
-
Betweenness centrality is widely used as a centrality measure, with applications across several disciplines. It is a measure that quantifies the importance of a vertex based on the vertex’s occurrence on shortest paths in a graph. This is a global measure, and in order to find the betweenness centrality of a node, one is supposed to have complete information about the graph. Most of the algorithms that are used to find betweenness centrality assume the constancy of the graph and are not efficient for dynamic networks. We propose a technique to update betweenness centrality of a graph when nodes are added or deleted. Observed experimentally, for real graphs, our algorithm speeds up the calculation of betweenness centrality from 7 to 412 times in comparison to the currently best-known techniques.
-
Betweenness Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen wide and increasing applications across several disciplines of late. In conjunction with the big data problems, there came the need to analyze large complex networks. Exact computation of a node’s betweenness is a daunting task in the networks of large size. In this paper, we propose a non-uniform sampling method to estimate the betweenness of a node. We apply our approach to estimate a node’s betweenness in several synthetic and real world graphs. We compare our method with the available techniques in the literature and show that our method fares several times better than the currently known techniques. We further show that the accuracy of our algorithm gets better with the increase in size and density of the network.
-
Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we study computationally, an approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation.
-
We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.
-
Betweenness centrality is a centrality measure that is widely used, with applications across several disciplines. It is a measure which quantifies the importance of a vertex based on its occurrence in shortest paths between all possible pairs of vertices in a graph. This is a global measure, and in order to find the betweenness centrality of a node, one is supposed to have complete information about the graph. Most of the algorithms that are used to find betwenness centrality assume the constancy of the graph and are not efficient for dynamic networks. We propose a technique to update betweenness centrality of a graph when nodes are added or deleted. Our algorithm experimentally speeds up the calculation of betweenness centrality (after updation) from 7 to 412 times, for real graphs, in comparison to the currently best known technique to find betweenness centrality.
Service Coverage Problem aims to find an ideal node for installing a service station in a given network such that services requested from various nodes are satisfied while minimizing the response time. Centrality Measures have been proved to be a salient computational science tool to find important nodes in networks. With increasing complexity and vividness in the network analysis problems, there is a need to modify the existing traditional centrality measures. In this paper we propose a new way of hybridizing centrality measures based on node-weighted centrality measures to address the service coverage problem.