David R. Karger
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
David R. Karger has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Cliff Stein
Dartmouth College
1 shared publication - Mikkel Thorup
University of Copenhagen, Copenhagen, Denmark
1 shared publication - Neal E. Young
Akamai Technologies Cambridge MA USA
1 shared publication - Philip N. Klein
Brown University
1 shared publication
Latest Publications
- Open Access
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even NP-hard to approximate within 1+delta for some small delta > 0. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
Open AccessRounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even NP-hard to approximate within 1+delta for some small delta > 0. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
- Open Access
Minimum Cuts in Near-Linear Time
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a ``semi-duality'' between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n^2 log n) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O(n^2 log^3 n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.
Open AccessMinimum Cuts in Near-Linear Time
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a ``semi-duality'' between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n^2 log n) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O(n^2 log^3 n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.
- Open Access
A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability.
Open AccessA Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability.
- 1 June 1998
- Published by Springer Nature in Mathematical Programming
- Vol. 82 (1-2) , 41-81
Random sampling and greedy sparsification for matroid optimization problems
- 1 June 1998
- Published by Springer Nature in Mathematical Programming
- Vol. 82 (1-2) , 41-81
Random sampling and greedy sparsification for matroid optimization problems