Arrow Research search

Author name cluster

Ramesh Hariharan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
2 author rows

Possible papers

22

NeurIPS Conference 2007 Conference Paper

A Randomized Algorithm for Large Scale Support Vector Learning

  • Krishnan Kumar
  • Chiru Bhattacharya
  • Ramesh Hariharan

We propose a randomized algorithm for large scale SVM learning which solves the problem by iterating over random subsets of the data. Crucial to the algorithm for scalability is the size of the subsets chosen. In the context of text classification we show that, by using ideas from random projections, a sample size of O(log n) can be used to obtain a solution which is close to the optimal with a high probability. Experiments done on synthetic and real life data sets demonstrate that the algorithm scales up SVM learners, without loss in accuracy.

PDF Details

STOC Conference 2007 Conference Paper

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

  • Ramesh Hariharan
  • Telikepalli Kavitha
  • Debmalya Panigrahi
  • Anand Bhalgat

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn). All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s -t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n 20/9 ) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n 20/9 n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Details

STOC Conference 2002 Conference Paper

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

  • Surender Baswana
  • Ramesh Hariharan
  • Sandeep Sen

We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O (1) query time, require O (\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O (n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O (n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O (n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O (\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O (1) time. This improves the previous best known update bound by a factor of log n . For maintaining all-pairs shortest paths, we present an algorithm that achieves O (\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O (\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0 , that achieves a sub-quadratic update time of O ( n log 2 n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O (1/ n c ) for any constant c ).

Details

FOCS Conference 1995 Conference Paper

Derandomizing Semidefinite Programming Based Approximation Algorithms

  • Sanjeev Mahajan
  • Ramesh Hariharan

Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-Complete problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-Bisection, k Vertex Coloring, Independent Set, etc. These breakthroughs all involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by M. Goemans and D. Williamson (1994). In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. Note that Goemans and Williamson also gave an elegant method to derandomize their Max-Cut algorithm. We show here that their technique has a fatal flaw. The techniques we subsequently develop are very different from theirs. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.

Details

FOCS Conference 1993 Conference Paper

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

  • Richard Cole 0001
  • Maxime Crochemore
  • Zvi Galil
  • Leszek Gasieniec
  • Ramesh Hariharan
  • S. Muthukrishnan 0001
  • Kunsoo Park
  • Wojciech Rytter

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching. >

Details

FOCS Conference 1992 Conference Paper

Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract)

  • Richard Cole 0001
  • Ramesh Hariharan

The paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n + O(n/m) character comparisons, following preprocessing. Specifically, the authors show an upper bound of n+8/3(m+1)(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m/sup 2/) time for preprocessing. In addition the following lower bounds are shown: for online algorithms, a bound of n+11/5(m+1) (n-m) character comparisons for m = 10 + 11 k, for any integer k >or= 1, and for general algorithms, a bound of n+2(n-m)/m+3 character comparisons, for m=2 k+l, for any integer k>or=1. >

Details