Главная

Ian Post

  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. 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.

  3. 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-материал