A simple linear time (1+/spl epsiv/)-approximation algorithm for k-means clustering in any dimensions A Kumar, Y Sabharwal, S Sen 45th Annual IEEE Symposium on Foundations of Computer Science, 454-462, 2004 | 357 | 2004 |

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs S Baswana, S Sen Random Structures & Algorithms 30 (4), 532-563, 2007 | 176 | 2007 |

Fully Dynamic Maximal Matching in Update Time S Baswana, M Gupta, S Sen SIAM Journal on Computing 44 (1), 88-113, 2015 | 147 | 2015 |

Linear-time approximation schemes for clustering problems in any dimensions A Kumar, Y Sabharwal, S Sen Journal of the ACM (JACM) 57 (2), 1-32, 2010 | 144 | 2010 |

Towards a theory of cache-efficient algorithms S Sen, S Chatterjee, N Dumir Journal of the ACM (JACM) 49 (6), 828-858, 2002 | 133 | 2002 |

An efficient output-sensitive hidden surface removal algorithm and its parallelization JH Reif, S Sen Proceedings of the fourth annual symposium on Computational geometry, 193-200, 1988 | 125 | 1988 |

Parallel sorting in two-dimensional VLSI models of computation ID Scherson, S Sen IEEE Transactions on Computers 38 (2), 238-249, 1989 | 114 | 1989 |

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths S Baswana, R Hariharan, S Sen Journal of Algorithms 62 (2), 74-92, 2007 | 104* | 2007 |

A Simple Linear Time Algorithm for Computing a (2*k* — 1)-Spanner of *O*(*n*^{1+1/k}) Size in Weighted GraphsS Baswana, S Sen International Colloquium on Automata, Languages, and Programming, 384-396, 2003 | 94 | 2003 |

Approximate distance oracles for unweighted graphs in expected O (n 2) time S Baswana, S Sen ACM Transactions on Algorithms (TALG) 2 (4), 557-577, 2006 | 92 | 2006 |

Cache-efficient matrix transposition S Chatterjee, S Sen Proceedings Sixth International Symposium on High-Performance Computer …, 2000 | 85 | 2000 |

Shear sort-a true two-dimensional sorting technique for VLSI networks S Isaacd, S Sandeep, AD Shamir International Conference on Parallel Processing, 903-908, 1986 | 73 | 1986 |

Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems JH Reif, S Sen SIAM Journal on Computing 21 (3), 466-485, 1992 | 68 | 1992 |

Optimal randomized parallel algorithms for computational geometry JH Reif, S Sen Algorithmica 7 (1), 91-117, 1992 | 66 | 1992 |

Polling: A new randomized sampling technique for computational geometry JH Reif, S Sen Proceedings of the twenty-first annual ACM symposium on Theory of computing …, 1989 | 58 | 1989 |

The distance bound for sorting on mesh-connected processor arrays is tight Y Ma, S Sen, ID Scherson 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), 255-263, 1986 | 54 | 1986 |

Random sampling techniques and parallel algorithms design S Rajasekaran, S Sen Synthesis of Parallel Algorithms, 411-451, 1993 | 53 | 1993 |

A simple D 2-sampling based PTAS for k-means and other clustering problems R Jaiswal, A Kumar, S Sen Algorithmica 70 (1), 22-46, 2014 | 49 | 2014 |

Linear time algorithms for clustering problems in any dimensions A Kumar, Y Sabharwal, S Sen International Colloquium on Automata, Languages, and Programming, 1374-1385, 2005 | 41 | 2005 |

Approximate distance oracles for unweighted graphs in Õ (*n*^{2}) timeS Baswana, S Sen Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete …, 2004 | 41 | 2004 |