N. S. Narayanaswamy

Dr. N. S. Narayanaswamy

orcid

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 August 2014 in Algorithmica
Verified
Journal Article
Closed access
PDF file
NNN. S. Narayanaswamy
N. S. Narayanaswamy
RSR. Subashini
R. Subashini

27 November 2021 in International Journal of Parallel Programming
Verified
Journal Article
Closed access
PDF file
RMRajesh Pandian Muniasamy
Rajesh Pandian Muniasamy
RNRupesh Nasre
Rupesh Nasre
NNN. S. Narayanaswamy
N. S. Narayanaswamy

19 October 2022 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MKManas Jyoti Kashyop
Manas Jyoti Kashyop
NNN. S. Narayanaswamy
N. S. Narayanaswamy
MNMeghana Nasre
Meghana Nasre
SPSai Mohith Potluri
Sai Mohith Potluri

19 December 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
NNN. S. Narayanaswamy
N. S. Narayanaswamy
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi
We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the Probabilistic-Core problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the Probabilistic-Core problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth.

13 June 2023 in Algorithmica
Verified
Journal Article
Closed access
PDF file
AAAkanksha Agrawal
Akanksha Agrawal
PCPratibha Choudhary
Pratibha Choudhary
NNN. S. Narayanaswamy
N. S. Narayanaswamy
KNK. K. Nisha
K. K. Nisha
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi

12 July 2023
Verified
Conference Paper
Open access
RMRajesh Pandian Muniasamy
Rajesh Pandian Muniasamy
SSSomesh Singh
Somesh Singh
RNRupesh Nasre
Rupesh Nasre
NNN. S. Narayanaswamy
N. S. Narayanaswamy
Capacitated Vehicle Routing Problem (CVRP) is an important combinatorial optimization problem, which is also NP-hard. A wide array of heuristics have been proposed in the literature to obtain an approximate solution to CVRP. To improve the execution time, parallel methods have been developed for accelerating metaheuristics-based algorithms, genetic algorithms, and evolutionary algorithms for CVRP. Despite these advances, our experiments with the state-of-the-art parallel solutions indicate that their run times are too high to be practically useful. The combinatorial explosion is so high that the execution time is prohibitively large even on mid-sized CVRP instances having a few hundred customers. In this work, we propose a novel technique which combines local search and randomization for solving CVRP faster with reasonable accuracy, even on large problem instances. Our usage of randomization enables searching a large space of candidate solutions. We experimentally compare our proposed method with the state-of-the-art GPU implementations on diverse input instances and demonstrate the efficacy of our approach. Our sequential and shared-memory parallel implementations are on an average 36--1189× faster than the state-of-the-art GPU-parallel genetic algorithms while also achieving a superior solution quality. Furthermore, our reported solutions are close to the current best-known solutions from CVRPLIB.