Arrow Research search

Author name cluster

David R. Karger

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.

48 papers
2 author rows

Possible papers

48

FOCS Conference 2017 Conference Paper

Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability

  • David R. Karger

Consider the problem of estimating the (un)reliability of an n-vertex graph when edges fail with probability p. We show that the Recursive Contraction Algorithms for minimum cuts, essentially unchanged and running in n 2+o(1) time, yields an unbiased estimator of constant relative variance (and thus an FPRAS with the same time bound) whenever p c -2. For larger p, we show that reliable graphs-where failures are rare so seemingly harder to find-effectively act like small graphs and can thus be analyzed quickly. Combining these ideas gives us an unbiased estimator for unreliability running in Õ(n 2. 78 ) time, an improvement on the previous Õ(n 3 ) time bound.

Details

FOCS Conference 2016 Conference Paper

A Fast and Simple Unbiased Estimator for Network (Un)reliability

  • David R. Karger

The following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently with probability 1- n -2/c, then (ii) recursively compute the disconnection probability of the resulting tiny graph if each edge fails with probability n 2/c p. We give a short, simple, self-contained proof that this estimator can be computed in linear time and has relative variance O(n 2 ). Combining these two facts with a standard sparsification argument yields an O(n 3 log n)-time algorithm for estimating the (un)reliability of a network. We also show how the technique can be used to create unbiased samples of disconnected networks.

Details

ICAPS Conference 2006 Conference Paper

Optimal Route Planning under Uncertainty

  • Evdokia Nikolova
  • Matthew Brand
  • David R. Karger

We present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for defining the optimal route: for a given source S and destination T in the graph, we seek an ST-path of lowest expected cost where the edge travel times are random variables and the cost is a nonlinear function of total travel time. Although this is a natural model for route-planning on real-world road networks, results are sparse due to the analytic difficulty of finding closed form expressions for the expected cost (Fan, Kalaba & Moore), as well as the computational/combinatorial difficulty of efficiently finding an optimal path which minimizes the expected cost. We identify a family of appropriate cost models and travel time distributions that are closed under convolution and physically valid. We obtain hardness results for routing problems with a given start time and cost functions with a global minimum, in a variety of deterministic and stochastic settings. In general the global cost is not separable into edge costs, precluding classic shortest-path approaches. However, using partial minimization techniques, we exhibit an efficient solution via dynamic programming with low polynomial complexity.

Details

FOCS Conference 2003 Conference Paper

Approximation Algorithms for Orienteering and Discounted-Reward TSP

  • Avrim Blum
  • Shuchi Chawla 0001
  • David R. Karger
  • Terran Lane
  • Adam Meyerson
  • Maria Minkoff

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E. M. Arkin (1998).

Details

FOCS Conference 2002 Conference Paper

Decoding Turbo-Like Codes via Linear Programming

  • Jon Feldman
  • David R. Karger

We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate (RA) codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length. Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where code words are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted code word.

Details

FOCS Conference 2000 Conference Paper

Building Steiner Trees with Incomplete Global Knowledge

  • David R. Karger
  • Maria Minkoff

A networking problem of present-day interest is that of distributing a single data item to multiple clients while minimizing network usage. Steiner tree algorithms are a natural solution method, but only when the set of clients requesting the data is known. We study what can be done without this global knowledge, when a given vertex knows only the probability that any other client wishes to be connected, and must simply specify a fixed path to the data to be used in case it is requested. Our problem is an example of a class of network design problems with concave cost functions (which arise when the design problem exhibits economies of scale). In order to solve our problem, we introduce a new version of the facility location problem: one in which every open facility is required to have some minimum amount of demand assigned to it. We present a simple bicriterion approximation for this problem, one which is loose in both assignment cost and minimum demand, but within a constant factor of the optimum for both. This suffices for our application. We leave open the question of finding an algorithm that produces a truly feasible approximate solution.

Details

FOCS Conference 1999 Conference Paper

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

  • Foto N. Afrati
  • Evripidis Bampis
  • Chandra Chekuri
  • David R. Karger
  • Claire Mathieu
  • Sanjeev Khanna
  • Ioannis Milis
  • Maurice Queyranne

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

Details

FOCS Conference 1994 Conference Paper

(De)randomized Construction of Small Sample Spaces in \calNC

  • David R. Karger
  • Daphne Koller

D. Koller and N. Megiddo (1993) introduced the paradigm of constructing compact distributions that satisfy a given set of constraints, and showed how it can be used to efficiently derandomize certain types of algorithm. In this paper, we significantly extend their results in two ways. First, we show how their approach can be applied to deal with more general expectation constraints. More importantly, we provide the first parallel (/spl Nscr//spl Cscr/) algorithm for constructing a compact distribution that satisfies the constraints up to a small relative error. This algorithm deals with constraints over any event that can be verified by finite automata, including all independence constraints as well as constraints over events relating to the parity or sum of a certain set of variables. Our construction relies on a new and independently interesting parallel algorithm for converting a solution to a linear system into an almost basic approximate solution to the same system. We use these techniques in the first /spl Nscr//spl Cscr/ derandomization of an algorithm for constructing large independent sets in d-uniform hypergraphs for arbitrary d. We also show how the linear programming perspective suggests new proof techniques which might be useful in general probabilistic analysis. >

Details

FOCS Conference 1994 Conference Paper

Approximate Graph Coloring by Semidefinite Programming

  • David R. Karger
  • Rajeev Motwani 0001
  • Madhu Sudan 0001

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We give a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with min {O(/spl Delta//sup 1/3/log/sup 4/3//spl Delta/), O(n/sup 1/4/ log n)} colors where /spl Delta/ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree /spl Delta/. This result can be generalized to k-colorable graphs to obtain a coloring using min {O/spl tilde/(/spl Delta//sup 1-2/k/), O/spl tilde/(n/sup 1-3/(k+1/))} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz /spl thetav/-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the /spl thetav/-function. >

Details

FOCS Conference 1993 Conference Paper

Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees

  • David R. Karger

Random sampling is a powerful way to gather information about a group by considering only a small part of it. We give a paradigm for applying this technique to optimization problems, and demonstrate its effectiveness on matroids. Matroids abstractly model many optimization problems that can be solved by greedy methods, such as the minimum spanning tree (MST) problem. Our results have several applications. We give an algorithm that uses simple data structures to construct an MST in O(m+n log n) time. We give bounds on the connectivity (minimum cut) of a graph suffering random edge failures. We give fast algorithms for packing matroid bases, with particular attention to packing spanning trees in graphs. >

Details

FOCS Conference 1991 Conference Paper

Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

  • David R. Karger
  • Daphne Koller
  • Steven J. Phillips

The all-pairs shortest paths problem in weighted graphs is investigated. An algorithm called the hidden paths algorithm, which finds these paths in time O(m*+n n/sup 2/ log n), where m* is the number of edges participating in shortest paths, is presented. It is argued that m* is likely to be small in practice, since m*=O(n log n) with high probability for many probability distributions on edge weights. An Omega (mn) lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest paths problem is proved. >

Details