Главная

Ashish Goel

  1. Liquidity in Credit Networks: A Little Trust Goes a Long Way.

    Втр, 07/06/2010 - 15:02 — SomNambul
    Authors: Ashish Goel, Ian Post, Pranav Dandekar, Ramesh Govindan
    Subjects: Computer Science and Game Theory
    Abstract

    Credit networks represent a way of modeling trust between entities in a
    network. Nodes in the network print their own currency and trust each other for
    a certain amount of each other's currency. This allows the network to serve as
    a decentralized payment infrastructure---arbitrary payments can be routed
    through the network by passing IOUs between trusting nodes in their respective
    currencies---and obviates the need for a common currency. Nodes can repeatedly
    transact with each other and pay for the transaction using trusted currency.

  2. Similarity Search and Locality Sensitive Hashing using TCAMs.

    Пт, 06/18/2010 - 15:01 — SomNambul
    Authors: Ashish Goel, Rajendra Shinde, Pankaj Gupta, Debojyoti Dutta
    Subjects: Databases
    Abstract

    Similarity search methods are widely used as kernels in various machine
    learning applications. Nearest neighbor search (NNS) algorithms are often used
    to retrieve similar entries, given a query. While there exist efficient
    techniques for exact query lookup using hashing, similarity search using exact
    nearest neighbors is known to be a hard problem and in high dimensions, best
    known solutions offer little improvement over a linear scan.

  3. One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk.

    Чт, 04/15/2010 - 15:01 — SomNambul
    Authors: Ashish Goel, Ian Post
    Subjects: Data Structures and Algorithms
    Abstract

    We study the single-sink buy-at-bulk problem with an unknown cost function.
    We want to route flow from a set of demand nodes to a root node, where the cost
    of routing x total flow along an edge is proportional to f(x) for some concave,
    non-decreasing function f satisfying f(0)=0. We present a simple, fast,
    deterministic, combinatorial algorithm that takes a set of demands and
    constructs a single tree T such that for all f the cost f(T) is a
    49.48-approximation of the optimal cost for that f.

  4. Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs.

    Пнд, 09/21/2009 - 13:59 — SomNambul
    Authors: Ashish Goel, Michael Kapralov, Sanjeev Khanna
    Subjects: Data Structures and Algorithms
    Abstract

    In this paper we consider the well-studied problem of finding a perfect
    matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The
    best-known algorithm for general bipartite graphs (due to Hopcroft and Karp)
    takes time O(m\sqrt{n}). In regular bipartite graphs, however, a matching is
    known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent
    line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved
    first to \tilde O(min{m, n^{2.5}/d}) and then to \tilde O(min{m, n^2/d}).

  5. An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk.

    Чт, 08/27/2009 - 13:23 — SomNambul
    Authors: Ashish Goel, Ian Post
    Subjects: Data Structures and Algorithms
    Abstract

    We consider the single-source (or single-sink) buy-at-bulk problem with an
    unknown concave cost function. We want to route a set of demands along a graph
    to or from a designated root node, and the cost of routing x units of flow
    along an edge is proportional to some concave, non-decreasing function f such
    that f(0) = 0. We present a polynomial time algorithm that finds a distribution
    over trees such that the expected cost of a tree for any f is within an
    O(1)-factor of the optimum cost for that f.

Math-arch

RSS-материал