Accueil

R. Ravi

  1. Geometry of Online Packing Linear Programs.

    Fri, 04/27/2012 - 15:01 — SomNambul
    Authors: R. Ravi, Marco Molinaro
    Subjects: Data Structures and Algorithms
    Abstract

    We consider packing LP's with $m$ rows where all constraint coefficients are
    normalized to be in the unit interval. The n columns arrive in random order and
    the goal is to set the corresponding decision variables irrevocably when they
    arrive so as to obtain a feasible solution maximizing the expected reward.
    Previous (1 - \epsilon)-competitive algorithms require the right-hand side of
    the LP to be Omega((m/\epsilon^2) log (n/\epsilon)), a bound that worsens with
    the number of columns and rows.

  2. Iterative rounding approximation algorithms for degree-bounded node-connectivity network design.

    Mon, 03/19/2012 - 15:01 — SomNambul
    Authors: R. Ravi, Takuro Fukunaga
    Subjects: Data Structures and Algorithms
    Abstract

    We consider the problem of finding a minimum edge cost subgraph of an
    undirected graph satisfying given connectivity requirements and degree bounds
    b(\dot) on nodes. We present an iterative rounding algorithm of the set-pair LP
    relaxation for this problem. When the solution is required to be k-connected
    spanning subgraph, our algorithm computes a solution that is an
    O(k)-approximation for the edge cost in which the degree of each node v is at
    most O(k)b(v).

  3. Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits.

    Mon, 02/21/2011 - 16:01 — SomNambul
    Authors: Anupam Gupta, R. Ravi, Ravishankar Krishnaswamy, Marco Molinaro
    Subjects: Data Structures and Algorithms
    Abstract

    In the stochastic knapsack problem, we are given a knapsack of size B, and a
    set of jobs whose sizes and rewards are drawn from a known probability
    distribution. However, we know the actual size and reward only when the job
    completes. How should we schedule jobs to maximize the expected total reward?
    We know O(1)-approximations when we assume that (i) rewards and sizes are
    independent random variables, and (ii) we cannot prematurely cancel jobs. What
    can we say when either or both of these assumptions are changed?

  4. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.

    Thu, 03/04/2010 - 16:01 — SomNambul
    Authors: Anupam Gupta, Viswanath Nagarajan, R. Ravi, Ravishankar Krishnaswamy
    Subjects: Data Structures and Algorithms
    Abstract

    We consider the problem of constructing optimal decision trees: given a
    collection of tests which can disambiguate between a set of $m$ possible
    diseases, each test having a cost, and the a-priori likelihood of the patient
    having any particular disease, what is a good adaptive strategy to perform
    these tests to minimize the expected cost to identify the disease? We settle
    the approximability of this problem by giving a tight $O(\log m)$-approximation
    algorithm. We also consider a more substantial generalization, the Adaptive TSP
    problem.

  5. Thresholded Covering Algorithms for Robust and Max-Min Optimization.

    Tue, 12/08/2009 - 16:01 — SomNambul
    Authors: Anupam Gupta, Viswanath Nagarajan, R. Ravi
    Subjects: Data Structures and Algorithms
    Abstract

    The general problem of robust optimization is this: one of several possible
    scenarios will appear tomorrow, but things are more expensive tomorrow than
    they are today. What should you anticipatorily buy today, so that the
    worst-case cost (summed over both days) is minimized? Feige et al. and
    Khandekar et al. considered the k-robust model where the possible outcomes
    tomorrow are given by all demand-subsets of size k, and gave algorithms for the
    set cover problem, and the Steiner tree and facility location problems in this
    model, respectively.

Math-arch

Syndicate content