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

STOC Conference 2020 Conference Paper

A phase transition and a quadratic time unbiased estimator for network reliability

  • David R. Karger

We improve the time for approximating network (un)reliability to ( n 2 ). We do so not with a new algorithm, but with a deeper analysis and tweaking of algorithms from our previous work. In particular, we show that once a graph’s failure probability shrinks below 1/2, the graph rapidly transitions to a regime where even the expected number of cut failures is small, and in fact is almost exactly the same as the graph’s failure probability. That is, we are very unlikely to ever see more than one cut fail. This lets us treat these cut failures as essentially independent, making it easier to estimate their likelihood. The contribution of this paper is not just the improved time bound, but also this clearer understanding of the evolution of a graph’s reliability. Our results rely on some new methods for analyzing the distribution of cut failures conditioned on the failure of a particular cut, as well as new insights into the evolution of a graph’s connectivity as edges are randomly added over time. Some of our results apply more broadly, to all monotone reliability systems.

Details

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

SODA Conference 2017 Conference Paper

Random Contractions and Sampling for Hypergraph and Hedge Connectivity

  • Mohsen Ghaffari 0001
  • David R. Karger
  • Debmalya Panigrahi

We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s-t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures.

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

STOC Conference 2009 Conference Paper

A nearly optimal oracle for avoiding failed vertices and edges

  • Aaron Bernstein
  • David R. Karger

We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The previous best algorithm produces an oracle of size ~O(n 2 ) that has an O(1) query time, and an ~O(n 2 √m) construction time. It was a randomized Monte Carlo algorithm that worked with high probability. Our oracle also has a constant query time and an ~O(n 2 ) space requirement, but it has an improved construction time of ~O(mn), and it is deterministic. Note that O(1) query, O(n 2 ) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.

Details

TCS Journal 2007 Journal Article

Subjective-cost policy routing

  • Joan Feigenbaum
  • David R. Karger
  • Vahab S. Mirrokni
  • Rahul Sami

We study a model of path-vector routing in which nodes’ routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance nodes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each node to have a route that nearly minimizes its subjective cost. We show that this scheme is trivially strategy proof and that it can be computed easily with a distributed algorithm. Furthermore, we prove a lower bound on the number of trees required to contain a ( 1 + ϵ ) -approximately optimal route for each node and show that our scheme is nearly optimal in this respect.

Details DOI

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

STOC Conference 2002 Conference Paper

Finding nearest neighbors in growth-restricted metrics

  • David R. Karger
  • Matthias Ruhl

Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. Spaces of this kind may occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.

Details

STOC Conference 2002 Conference Paper

Random sampling in residual graphs

  • David R. Karger
  • Matthew S. Levine

Consider an n -vertex, m -edge, undirected graph with maximum flow value v . We give a new Õ ( m+nv )-time maximum flow algorithm based on finding augmenting paths in random samples of the edges of residual graphs. After assigning certain special sampling probabilities to edges in Õ ( m ) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.

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