From Bibliography of the proceedings of many conferences (pldi97):
@InProceedings{1997:pldi:young,
author = "Cliff Young and David S. Johnson and Michael D. Smith
and David R. Karger",
title = "Near-Optimal Intraprocedural Branch Alignment",
booktitle = "Proceedings of the 1997 {ACM} {SIGPLAN} Conference on
Programming Language Design and Implementation",
year = "1997",
pages = "183--193",
url = "http://www.acm.org/pubs/articles/proceedings/pldi/258915/p183-young/p183-young.pdf",
genterms = "ALGORITHMS, DESIGN, EXPERIMENTATION, LANGUAGES,
MEASUREMENT, PERFORMANCE, STANDARDIZATION, THEORY",
categories = "C.1.2 Computer Systems Organization, PROCESSOR
ARCHITECTURES, Multiple Data Stream Architectures
(Multiprocessors), Pipeline processors**. D.3.4
Software, PROGRAMMING LANGUAGES, Processors, Compilers.
G.1.6 Mathematics of Computing, NUMERICAL ANALYSIS,
Optimization. K.6.2 Computing Milieux, MANAGEMENT OF
COMPUTING AND INFORMATION SYSTEMS, Installation
Management, Benchmarks. G.4 Mathematics of Computing,
MATHEMATICAL SOFTWARE, Algorithm design and analysis.",
annote = "incomplete",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@Article{ALGOR::KargerMR1997,
title = "On Approximating the Longest Path in a Graph",
author = "David R. Karger and Rajeev Motwani and G. D. S.
Ramkumar",
journal = "Algorithmica",
pages = "82--98",
month = may,
year = "1997",
volume = "18",
number = "1",
}
From Bibliography of "Algorithmica":
@InProceedings{Arora+Karger+Karpinski+1995a,
author = "Sanjeev Arora and David R. Karger and Marek
Karpinski",
title = "Polynomial Time Approximation Schemes for Dense
Instances of {$\cal{NP}$}-Hard Problems",
booktitle = "Proc. 27th ACM Symp. Theory of Computing, STOC",
pages = "284--293",
year = "1995",
seealso = "\cite{Arora+Karger+Karpinski+1998a}",
acm-portal-url = "http://portal.acm.org/citation.cfm?id=225140",
compressed-postscript-url = "http://theory.cs.bonn.edu/~marek/publications/AKK_STOC95.ps.Z",
compressed-postscript-url = "http://theory.lcs.mit.edu/~karger/Papers/dense.ps.Z",
pdf-doc = "00001207.pdf",
postscript-doc = "00001149.ps",
}
From Bibliography on Computational Intelligence and Efficient Algorithms:
@TechReport{Arora+Karger+Karpinski+1998a,
author = "Sanjeev Arora and David R. Karger and Marek
Karpinski",
title = "Polynomial Time Approximation Schemes for Dense
Instances of {$\cal{NP}$}-Hard Problems (Extended
Version)",
institution = "Institut f{\"u}r Informatik, Rheinische
Friedrich-Wilhelms-Universit{\"a}t Bonn",
type = "CS-Report",
number = "85195",
year = "1998",
abstract = "We present a unified framework for designing
polynomial time approximation schemes (PTASs) for
``dense'' instances of many $\cal{NP}$-hard
optimization problems, including maximum cut, graph
bisection, graph separation, minimum $k$-way cut with
and without specified terminals, and maximum
3-satisfiability. By dense graphs we mean graphs with
minimum degree $\Omega(n)$, although our algorithms
solve most of these problems so long as the average
degree is $\Omega(n)$. Denseness for non-graph problems
is defined similarly. The unified framework begins with
the idea of {\em exhaustive sampling:} picking a small
random set of vertices, guessing where they go on the
optimum solution, and then using their placement to
determine the placement of everything else. The
approach then develops into a PTAS for approximating
certain {\em smooth\/} integer programs where the
objective function and the constraints are ``dense''
polynomials of constant degree.",
seealso = "\cite{Arora+Karger+Karpinski+1995a}",
gzipped-postscript-url = "ftp://theory.cs.uni-bonn.de/pub/reports/cs-reports/1998/85195-CS.ps.gz",
postscript-doc = "00001150.ps",
}
From Bibliography of the proceedings of many conferences (cikm99):
@InProceedings{Arora:1995:PTA,
author = "Sanjeev Arora and David Karger and Marek Karpinski",
title = "Polynomial time approximation schemes for dense
instances of {NP}-hard problems",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-seventh annual {ACM}
Symposium on Theory of Computing: Las Vegas, Nevada,
May 29--June 1, 1995",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1995",
ISBN = "0-89791-718-9",
pages = "284--293",
year = "1995",
bibdate = "Wed Apr 4 18:53:19 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/225058/p284-arora/;
http://www.acm.org/pubs/articles/proceedings/stoc/225058/p284-arora/p284-arora.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (soda94):
@InProceedings{Benczur:1996:AMC,
author = "Andr{\'a}s A. Bencz{\'u}r and David R. Karger",
title = "Approximating $s$--$t$ minimum cuts in {$O(n2)$}
time",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-eighth annual {ACM}
Symposium on the Theory of Computing, Philadelphia,
Pennsylvania, May 22--24, 1996",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1996",
ISBN = "0-89791-785-5",
pages = "47--55",
year = "1996",
bibdate = "Wed Apr 4 18:53:19 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/237814/p47-benczur/;
http://www.acm.org/pubs/articles/proceedings/stoc/237814/p47-benczur/p47-benczur.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of "Journal of Algorithms":
@Article{Blum:1997:CAC,
author = "Avrim Blum and David Karger",
title = "An {$\mbox{\~O}(n^{3/14})$}-coloring algorithm for
$3$-colorable graphs",
journal = "Information Processing Letters",
volume = "61",
number = "1",
pages = "49--53",
day = "14",
month = jan,
year = "1997",
coden = "IFPLAT",
ISSN = "0020-0190",
mrclass = "05C15 (05C85)",
mrnumber = "97k:05068",
bibdate = "Wed Nov 11 12:16:26 MST 1998",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240C
(Computational complexity)",
corpsource = "Sch. of Comput. Sci., Carnegie Mellon Univ.,
Pittsburgh, PA, USA",
keywords = "computational complexity; graph colouring; n-node
3-colorable graph; O(n/sup 3/14/)-coloring algorithm;
polynomial-time algorithm",
treatment = "T Theoretical or Mathematical",
}
From Bibliography of Technical Reports: Dartmouth College:
@InProceedings{CIKM99*413,
author = "Eytan Adar and David Karger",
title = "Haystack: Per-User Information Environments",
pages = "413--422",
booktitle = "Proceedings of the 8th International Conference on
Information Knowledgement ({CIKM}-99)",
month = nov # "~2--6",
publisher = "ACM Press",
address = "N.Y.",
year = "2000",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@InProceedings{Cutting92,
author = "Douglass R. Cutting and David R. Karger and Jan O.
Pedersen and John W. Tukey",
title = "Scatter/Gather: {A} Cluster-Based Approach to Browsing
Large Document Collections",
booktitle = "Proceedings of the Fifteenth Annual International ACM
SIGIR Conference on Research and Development in
Information Retrieval",
series = "Interface Design and Display",
pages = "318--329",
year = "1992",
copyright = "(c) Copyright 1992 Association for Computing
Machinery",
mrnumber = "C.IR.92.318",
url = "http://www.acm.org/pubs/articles/proceedings/ir/133160/p318-cutting/p318-cutting.pdf",
abstract = "Document clustering has not been well received as an
information retrieval tool. Objections to its use fall
into two main categories: first, that clustering is too
slow for large corpora (with running time often
quadratic in the number of documents); and second, that
clustering does not appreciably improve retrieval. We
argue that these problems arise only when clustering is
used in an attempt to improve conventional search
techniques. However, looking at clustering as an
information access tool in its own right obviates these
objections, and provides a powerful new access
paradigm. We present a document browsing technique that
employs document clustering as its primary operation.
We also present fast (linear time) clustering
algorithms which support this interactive browsing
paradigm.",
}
From Bibliography of "IEEE Symposium on Foundations of Computer Science":
@InProceedings{Cutting93,
author = "Douglass R. Cutting and David R. Karger and Jan O.
Pedersen",
title = "Constant Interaction-Time Scatter/Gather Browsing of
Very Large Document Collections",
booktitle = "Proceedings of the Sixteenth Annual International ACM
SIGIR Conference on Research and Development in
Information Retrieval",
series = "Association Methods",
pages = "126--134",
year = "1993",
copyright = "(c) Copyright 1993 Association for Computing
Machinery",
mrnumber = "C.IR.93.126",
url = "http://www.acm.org/pubs/articles/proceedings/ir/160688/p126-cutting/p126-cutting.pdf",
abstract = "The Scatter/Gather document browsing method uses fast
document clustering to produce table-of-contents-like
outlines of large document collections. Previous work
[1] developed linear-time document clustering
algorithms to establish the feasibility of this method
over moderately large collections. However, even
linear-time algorithms are too slow to support
interactive browsing of very large collections such as
Tipster, the DARPA standard text retrieval evaluation
collection. We present a scheme that supports constant
interaction-time Scatter/Gather of arbitrarily large
collections after near-linear time preprocessing. This
involves the construction of a cluster hierarchy. A
modification of Scatter/Gather employing this scheme,
and an example of its use over the Tipster collection
are presented.",
}
From Bibliographies of various confererences in the area of computer architecture, compilers and related fields:
@InProceedings{Dabek:2001:BPP,
author = "Frank Dabek and Emma Brunskill and M. Frans Kaashoek
and David Karger and Robert Morris and Ion Stoica and
Hari Balakrishnan",
title = "Building Peer-to-Peer Systems with {Chord}, a
Distributed Lookup Service",
editor = "IEEE",
booktitle = "{Eighth IEEE Workshop on Hot Topics in Operating
Systems (HotOS-VIII). May 20--23, 2001, Schloss Elmau,
Germany}",
publisher = "IEEE Computer Society Press",
address = "1109 Spring Street, Suite 300, Silver Spring, MD
20910, USA",
year = "2001",
ISBN = "0-7695-1040-X",
pages = "81--86",
year = "2001",
bibdate = "Fri Feb 22 11:41:03 MST 2002",
url = "http://www.pdos.lcs.mit.edu/cgi-bin/bibtex-entry.cgi?key=chord:hotos",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (soda01):
@InProceedings{Engels:2001:PPS,
author = "Daniel W. Engels and Jon Feldman and David R. Karger
and Matthias Ruhl",
booktitle = "Twelfth Annual Symposium on Discrete algorithms",
title = "Parallel processor scheduling with delay constraints",
publisher = "ACM Press",
address = "New York, NY, USA",
pages = "577--585",
year = "2001",
ISBN = "0-89871-490-7",
LCCN = "????",
bibdate = "Thu Jul 26 19:24:11 2001",
url = "http://delivery.acm.org/10.1145/370000/365538/p577-engels.pdf",
acknowledgement = ack-nhfb,
doi = "0.1145.365538",
keywords = "IA-64",
}
From Bibliography on halving lines, k-sets, and parametric matroid optimization:
@InProceedings{FOCS::KargerK1994,
title = "({D}e)randomized Construction of Small Sample Spaces
in {$\cal{NC}$}",
author = "David R. Karger and Daphne Koller",
pages = "252--263",
booktitle = "35th Annual Symposium on Foundations of Computer
Science",
month = "20--22 " # nov,
year = "1994",
address = "Santa Fe, New Mexico",
organization = "IEEE",
}
From Bibliography of the proceedings of many conferences (soda94):
@Article{Fizzano:1997:DJS,
author = "Perry Fizzano and David Karger and Clifford Stein and
Joel Wein",
title = "Distributed Job Scheduling in Rings",
journal = "Journal of Parallel and Distributed Computing",
volume = "45",
number = "2",
pages = "122--133",
day = "15",
month = sep,
year = "1997",
coden = "JPDCER",
ISSN = "0743-7315",
bibdate = "Thu Mar 9 09:19:03 MST 2000",
url = "http://www.idealibrary.com/links/doi/10.1006/jpdc.1997.1373/production;
http://www.idealibrary.com/links/doi/10.1006/jpdc.1997.1373/production/pdf;
http://www.idealibrary.com/links/doi/10.1006/jpdc.1997.1373/production/ref",
acknowledgement = ack-nhfb,
doi = "10.1006/jpdc.1997.1373",
}
From Bibliography of the proceedings of many conferences (stoc98):
@InProceedings{FizzanoEtAl94,
author = "Perry Fizzano and David Karger and Clifford Stein and
Joel Wein",
title = "Job Scheduling in Rings",
booktitle = "Proceedings of the 6th Annual {ACM} Symposium on
Parallel Algorithms and Architectures",
address = "Cape May, New Jersey",
organization = "SIGACT and SIGARCH",
month = jun # " 27--29,",
year = "1994",
pages = "210--219",
}
From Annotated Bibliography of Digital Library Related Sources:
@TechReport{ICSI-TR-95-011,
author = "Sanjev Arora and David Karger and Marek Karpinski",
title = "Polynomial Time Approximation Schemes for Dense
Instances of $\NP$-Hard Problems",
institution = "International Computer Science Institute",
number = "TR-95-011",
address = "Berkeley, CA",
month = mar,
year = "1995",
abstract = "We present a unified framework for designing
polynomial time approximation schemes (PTASs) for
``dense'' instances of many $\NP$-hard optimization
problems, including maximum cut, graph bisection, graph
separation, minimum $k$-way cut with and without
specified sources, and maximum 3-satisfiability. Dense
graphs for us are graphs with minimum degree
$\Theta(n)$, although some of our algorithms work so
long as the graph is dense ``on average''. (Denseness
for non-graph problems is defined similarly.) The
unified framework begins with the idea of {\em
exhaustive sampling:} picking a small random set of
vertices, guessing where they go on the optimum
solution, and then using their placement to determine
the placement of everything else. The approach then
develops into a PTAS for approximating certain {\em
smooth\/} integer programs where the objective function
is a ``dense'' polynomial of constant degree.",
}
From Bibliography of "Information Processing Letters":
@Article{IPL::BlumK1997,
title = "An {$\tilde{O}(n^{3/14})$}-coloring algorithm for
3-colorable graphs",
author = "Avrim Blum and David Karger",
pages = "49--53",
journal = "Information Processing Letters",
month = "14~" # jan,
year = "1997",
volume = "61",
number = "1",
references = "\cite{STOC::blum1989} \cite{JACM::Blum1994}
\cite{STOC::BellareS1994} \cite{FOCS::KargerMS1994}
\cite{ACTAI::MonienS1985} \cite{JACM::Wigderson1983}",
}
From Bibliography of the proceedings of many conferences (stoc94):
@Article{JACM::KargerKT1995,
title = "A Randomized Linear-Time Algorithm to Find Minimum
Spanning Trees",
author = "David R. Karger and Philip N. Klein and Robert E.
Tarjan",
area = "Complexity of Algorithms",
pages = "321--328",
journal = "Journal of the ACM",
month = mar,
year = "1995",
volume = "42",
number = "2",
general-terms = "Algorithms",
keywords = "Matroid, minimum spanning tree, network, randomized
algorithm",
cr-categories = "F.2.2[computations on discrete structures];
G.2.2[graph algorithms, network problems, trees];
G.3[probabilistic algorithms (including Monte Carlo)],
I.5.3",
references = "\cite{FOCS::ColeV1986} \cite{FOCS::FredmanW1990}
\cite{FOCS::GabowGS1984} \cite{FOCS::Karger1993}
\cite{STOC::KleinT1994} \cite{JACM::Tarjan1979}",
}
From Bibliography of the proceedings of many conferences (soda01):
@Article{JACM::KargerMS1998,
title = "Approximate Graph Coloring by Semidefinite
Programming",
author = "David Karger and Rajeev Motwani and Madhu Sudan",
area = "Complexity of Algorithms",
journal = "Journal of the ACM",
pages = "246--265",
month = mar,
year = "1998",
volume = "45",
number = "2",
keywords = "Approximation algorithms, chromatic number, graph
coloring, NP-completeness, randomized algorithms",
general-terms = "Algorithms, Optimization, Theory",
cr-categories = "F.2.2; G.2.1; G.2.2",
references = "\cite{STOC::AlonK1994} \cite{FOCS::AroraLMSS1992}
\cite{STOC::BellareS1994} \cite{JACM::blum1994}
\cite{IPL::blumK1997} \cite{PLDI::BriggsCKT1989}
\cite{STOC::Feige1995} \cite{JACM::FeigeGLSS1996}
\cite{SCTC::FeigeK1996} \cite{JACM::GoemansW1995}
\cite{IPL::halldorsson1993} \cite{FOCS::Hastad1996}
\cite{ISTC::KhannaLS1992} \cite{FOCS::KhannaMSV1994}
\cite{IEEETIT::Lovasz1979} \cite{STOC::LundY1993}
\cite{FOCS::MahajanR1995} \cite{FOCS::Szegedy1994}
\cite{JACM::Wigderson1983}",
}
From Richard Webber's Research Bibliography:
@Article{JACM::KargerS1996,
title = "A New Approach to the Minimum Cut Problem",
author = "David R. Karger and Clifford Stein",
area = "Complexity of Algorithms",
journal = "Journal of the ACM",
pages = "601--640",
month = jul,
year = "1996",
volume = "43",
number = "4",
keywords = "Graph algorithm, minimum cut, network reliability,
parallel computing, randomized algorithm",
cr-categories = "F.2.2; G.2.2[graph algorithms \and network problems];
G.3[probabilistic algorithms (including Monte Carlo)];
I.1.2",
general-terms = "Algorithms",
references = "\cite{STOC::Benczur1994} \cite{STOC::BenczurK1996}
\cite{SICOMP::CookDR1986} \cite{FOCS::CheriyanH1989}
\cite{SICOMP::CheriyanH1995}
\cite{STOC::DahlhausJPSY1992}
\cite{SICOMP::DahlhausJPSY1994}
\cite{JACM::EdmondsK1972} \cite{FOCS::Gabow1991}
\cite{STOC::Gabow1991} \cite{JCSS::Gabow1995}
\cite{FOCS::GoldschmidtH1988}
\cite{TCS::GoldschlagerSS1982}
\cite{JACM::GoldbergT1988} \cite{STOC::Hastad1986}
\cite{SODA::HaoO1992} \cite{JALGO::HaoO1994}
\cite{SODA::Karger1993} \cite{STOC::Karger1994}
\cite{THESIS::Karger1994} \cite{SODA::Karger1994}
\cite{STOC::Karger1995} \cite{STOC::Karger1996}
\cite{STOC::KargerM1994} \cite{SICOMP::KargerM1996}
\cite{STOC::KleinST1990} \cite{SICOMP::KleinPST1994}
\cite{SODA::KingRT1992} \cite{JALGO::KingRT1994}
\cite{SICOMP::KhullerS1991} \cite{STOC::KargerS1993}
\cite{FOCS::Matula1987} \cite{SODA::Matula1993}
\cite{STOC::PhillipsW1993} \cite{JCSS::SleatorT1983}
\cite{JALGO::ShiloachV1982}",
}
From Bibliography of Technical Reports: University of Bonn, Department of Computer Science:
@Article{JALGO::KargerPT1996,
title = "A Better Algorithm for an Ancient Scheduling Problem",
author = "David R. Karger and Steven J. Phillips and Eric
Torng",
pages = "400--430",
journal = "Journal of Algorithms",
year = "1996",
month = mar,
volume = "20",
number = "2",
references = "\cite{FOCS::AzarBK1992} \cite{STOC::BartalFKV1992}",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@Article{JCSS::KargerK1997,
title = "{(De)randomized} Construction of Small Sample Spaces
in~{$\mathcal{NC}$}",
author = "David R. Karger and Daphne Koller",
pages = "402--413",
journal = "Journal of Computer and System Sciences",
year = "1997",
month = dec,
volume = "55",
number = "3",
preliminary = "focs::KargerK1994",
references = "\cite{JALGO::AlonBI1986} \cite{FOCS::AlonGH1990}
\cite{FOCS::blumG1992} \cite{JACM::BergerR1991}
\cite{FOCS::ChorGHFRS1985} \cite{STOC::EvenGLNV1992}
\cite{STOC::KollerM1993} \cite{STOC::KarloffM1994}
\cite{STOC::LubyN1993} \cite{SICOMP::Luby1986}
\cite{FOCS::MotwaniNN1989} \cite{STOC::Nisan1990}
\cite{SICOMP::NaorN1993} \cite{STOC::Schulman1992}",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@Article{JPDC::FizzanoKSW1997,
title = "Distributed Job Scheduling in Rings",
author = "Perry Fizzano and David Karger and Clifford Stein and
Joel Wein",
pages = "122--133",
journal = "Journal of Parallel and Distributed Computing",
year = "1997",
month = "15~" # sep,
volume = "45",
number = "2",
references = "\cite{STOC::AielloAMR1993} \cite{FOCS::AlonKRS1992}
\cite{JACM::AttiyaSW1988} \cite{STOC::AwerbuchKP1992}
\cite{SPAA::GhoshM1994} \cite{SPAA::GhoshMS1996}
\cite{SPAA::HerlihyLS1992} \cite{SODA::HoppeT1995}
\cite{CACM::HummelSF1992} \cite{IEEETSE::LinK1987}
\cite{JALGO::MansourS1990}
\cite{STOC::PapadimitriouY1988}
\cite{SWAT::PhillipsSW1994} \cite{FOCS::Vaidya1989}",
}
From Bibliography of the proceedings of many conferences (soda98):
@Article{KarKleTar-JACM-95,
title = "{A randomized linear-time algorithm for finding
minimum spanning trees}",
author = "David Karger and Philip N. Klein and Robert E.
Tarjan",
keywords = "minimum spanning tree",
journal = "J. Assoc. Comput. Mach.",
publisher = "ACM",
volume = "42",
pages = "321--329",
year = "1995",
}
From Bibliography on Computational Intelligence and Efficient Algorithms:
@Article{Karger:1993:FHP,
author = "David R. Karger and Daphne Koller and Steven J.
Phillips",
title = "Finding the Hidden Path: Time Bounds for All-Pairs
Shortest Paths",
journal = "SIAM Journal on Computing",
volume = "22",
number = "6",
pages = "1199--1217",
month = dec,
year = "1993",
coden = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
mrclass = "05C85 (68Q25)",
mrnumber = "95j:05158",
bibdate = "Sat Jan 18 18:03:50 MST 1997",
acknowledgement = ack-nhfb,
}
From Bibliography of the journal SIAM Review:
@InProceedings{Karger:1994:DTA,
author = "David R. Karger and Rajeev Motwani",
title = "Derandomization through approximation: an {NC}
algorithm for minimum cuts",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-sixth annual {ACM} Symposium
on the Theory of Computing: Montreal, Quebec, Canada,
May 23--25, 1994",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1994",
ISBN = "0-89791-663-8",
pages = "497--506",
year = "1994",
bibdate = "Wed Apr 4 18:53:18 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/195058/p497-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/195058/p497-karger/p497-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of "ACM Symposium on Theory of Computing":
@InProceedings{Karger:1994:RSC,
author = "David R. Karger",
title = "Random sampling in cut, flow, and network design
problems",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-sixth annual {ACM} Symposium
on the Theory of Computing: Montreal, Quebec, Canada,
May 23--25, 1994",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1994",
ISBN = "0-89791-663-8",
pages = "648--657",
year = "1994",
bibdate = "Wed Apr 4 18:53:18 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/195058/p648-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/195058/p648-karger/p648-karger.pdf",
acknowledgement = ack-nhfb,
}
From Software Engineering and Programming Languages Citation Bibliography:
@InProceedings{Karger:1995:AMC,
author = "David Karger and Serge Plotkin",
title = "Adding multiple cost constraints to combinatorial
optimization problems, with applications to
multicommodity flows",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-seventh annual {ACM}
Symposium on Theory of Computing: Las Vegas, Nevada,
May 29--June 1, 1995",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1995",
ISBN = "0-89791-718-9",
pages = "18--25",
year = "1995",
bibdate = "Wed Apr 4 18:53:19 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/225058/p18-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/225058/p18-karger/p18-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (stoc96):
@InProceedings{Karger:1995:RFP,
author = "David R. Karger",
title = "A randomized fully polynomial time approximation
scheme for the all terminal network reliability
problem",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-seventh annual {ACM}
Symposium on Theory of Computing: Las Vegas, Nevada,
May 29--June 1, 1995",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1995",
ISBN = "0-89791-718-9",
pages = "11--17",
year = "1995",
bibdate = "Wed Apr 4 18:53:19 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/225058/p11-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/225058/p11-karger/p11-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (spaa92):
@Article{Karger:1995:RLA,
author = "David R. Karger and Philip N. Klein and Robert E.
Tarjan",
title = "A Randomized Linear-Time Algorithm to Find Minimum
Spanning Trees",
journal = "Journal of the ACM",
volume = "42",
number = "2",
pages = "321--328",
month = mar,
year = "1995",
coden = "JACOAH",
ISSN = "0004-5411",
bibdate = "Wed Aug 30 20:17:10 1995",
url = "http://www.acm.org/pubs/toc/Abstracts/0004-5411/201022.html",
abstract = "We present a randomized linear-time algorithm to find
a minimum spanning tree in a connected graph with edge
weights. The algorithm uses random sampling in
combination with a recently discovered linear-time
algorithm for verifying a minimum spanning tree. Our
computational model is a unit-cost random-access
machine with the restriction that the only operations
allowed on edge weights are binary comparisons.",
acknowledgement = ack-nhfb,
keywords = "algorithms",
subject = "{\bf G.2.2}: Mathematics of Computing, DISCRETE
MATHEMATICS, Graph Theory, Graph algorithms. {\bf
F.2.2}: Theory of Computation, ANALYSIS OF ALGORITHMS
AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and
Problems, Computations on discrete structures. {\bf
G.3}: Mathematics of Computing, PROBABILITY AND
STATISTICS, Probabilistic algorithms (including Monte
Carlo). {\bf I.5.3}: Computing Methodologies, PATTERN
RECOGNITION, Clustering. {\bf G.2.2}: Mathematics of
Computing, DISCRETE MATHEMATICS, Graph Theory, Network
problems. {\bf G.2.2}: Mathematics of Computing,
DISCRETE MATHEMATICS, Graph Theory, Trees.",
}
From Bibliography of the SIAM Journal on Computing:
@InProceedings{Karger:1996:MCN,
author = "David R. Karger",
title = "Minimum cuts in near-linear time",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-eighth annual {ACM}
Symposium on the Theory of Computing, Philadelphia,
Pennsylvania, May 22--24, 1996",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1996",
ISBN = "0-89791-785-5",
pages = "56--63",
year = "1996",
bibdate = "Wed Apr 4 18:53:19 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/237814/p56-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/237814/p56-karger/p56-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of "ACM Symposium on Theory of Computing":
@Article{Karger:1996:NAM,
author = "David R. Karger and Clifford Stein",
title = "A new approach to the minimum cut problem",
journal = "Journal of the ACM",
volume = "43",
number = "4",
pages = "601--640",
month = jul,
year = "1996",
coden = "JACOAH",
ISSN = "0004-5411",
mrclass = "68R10 (68Q25)",
mrnumber = "1 409 212",
bibdate = "Tue Sep 09 07:55:44 1997",
url = "http://www.acm.org/pubs/toc/Abstracts/jacm/234534.html",
abstract = "This paper present a new approach to finding minimum
cuts in undirected graphs. The fundamental principle is
simple: the edges in a graph's minimum cut form an
extremely small fraction of the graph's edges. Using
this idea, we give a randomized, strongly polynomial
algorithm that finds the minimum cut in an arbitrarily
weighted undirected graph with high probability. The
algorithm runs in $O(n^{2}\log^{3}n)$ time, a
significant improvement over the previous $\~O(mn)$
time bounds based on maximum flows. It is simple and
intuitive and uses no complex data structures. Our
algorithm can be parallelized to run in {\em RNL\/}
with $n^{2}$ processors; this gives the first proof
that the minimum cut problem can be solved in {\em
RNL}. The algorithm does more than find a single
minimum cut; it finds all of them.\par With minor
modifications, our algorithm solves two other problems
of interest. Our algorithm finds all cuts with value
within a multiplicative factor of [alpha] of the
minimum cut's in expected $\~O(n^{2[alpha]})$ time, or
in {\em RNL\/} with $n^{2[alpha]}$ processors. The
problem of finding a minimum multiway cut of graph into
$r$ pieces is solved in expected $\~O(n^{2(r-1)})$
time, or in {\em RNL\/} with $n^{2(r-1)}$ processors.
The ``trace'' of the algorithm's execution on these two
problems forms a new compact data structure for
representing all small cuts and all multiway cuts in a
graph. This data structure can be efficiently
transformed into the more standard cactus representing
for minimum cuts.",
acknowledgement = ack-nhfb,
keywords = "algorithms",
subject = "{\bf F.2.2}: Theory of Computation, ANALYSIS OF
ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical
Algorithms and Problems. {\bf G.2.2}: Mathematics of
Computing, DISCRETE MATHEMATICS, Graph Theory, Graph
algorithms. {\bf G.2.2}: Mathematics of Computing,
DISCRETE MATHEMATICS, Graph Theory, Network problems.
{\bf G.3}: Mathematics of Computing, PROBABILITY AND
STATISTICS, Probabilistic algorithms (including Monte
Carlo). {\bf I.1.2}: Computing Methodologies, ALGEBRAIC
MANIPULATION, Algorithms.",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@Article{Karger:1997:AMC,
author = "David R. Karger and Rajeev Motwani",
title = "An {${\rm NC}$} Algorithm for Minimum Cuts",
journal = "SIAM Journal on Computing",
volume = "26",
number = "1",
pages = "255--272",
month = feb,
year = "1997",
coden = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
mrclass = "68Q22 (68Q25)",
mrnumber = "97m:68083",
bibdate = "Sat Dec 5 17:26:53 MST 1998",
url = "http://epubs.siam.org/sam-bin/dbq/article/27308",
acknowledgement = ack-nhfb,
classification = "C1140Z (Other topics in statistics); C1160
(Combinatorial mathematics); C1180 (Optimisation
techniques); C4240P (Parallel programming and algorithm
theory)",
corpsource = "Lab. for Comput. Sci., MIT, Cambridge, MA, USA",
keywords = "constant factor; derandomization; expanders; graph
theory; minimisation; minimum cut problem; minimum
k-way cuts; natural combinatorial set isolation
problem; NC algorithm; pairwise independence; parallel
algorithms; polylogarithmic values; polynomially
bounded values; random processes; random walks;
randomised algorithms; randomized reduction; RNC
solution; set theory; sparse k-connectivity
certificate; weighted undirected graphs",
treatment = "T Theoretical or Mathematical",
}
From Bibliography of the SIAM Journal on Computing:
@InProceedings{Karger:1997:CHR,
author = "David Karger and Eric Lehman and Tom Leighton and Rina
Panigrahy and Matthew Levine and Daniel Lewin",
title = "Consistent hashing and random trees: distributed
caching protocols for relieving hot spots on the {World
Wide Web}",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-ninth annual {ACM} Symposium
on the Theory of Computing: El Paso, Texas, May 4--6,
1997",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1997",
ISBN = "0-89791-888-6",
pages = "654--663",
year = "1997",
bibdate = "Wed Apr 4 18:53:20 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/258533/p654-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/258533/p654-karger/p654-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (mobicom00):
@InProceedings{Karger:1997:URS,
author = "David R. Karger",
title = "Using random sampling to find maximum flows in
uncapacitated undirected graphs",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-ninth annual {ACM} Symposium
on the Theory of Computing: El Paso, Texas, May 4--6,
1997",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1997",
ISBN = "0-89791-888-6",
pages = "240--249",
year = "1997",
bibdate = "Wed Apr 4 18:53:20 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/258533/p240-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/258533/p240-karger/p240-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography for the SIGPLAN Notices:
@Article{Karger:1998:AGC,
author = "David Karger and Rajeev Motwani and Madhu Sudan",
title = "Approximate graph coloring by semidefinite
programming",
journal = "Journal of the ACM",
volume = "45",
number = "2",
pages = "246--265",
month = mar,
year = "1998",
coden = "JACOAH",
ISSN = "0004-5411",
bibdate = "Sat May 16 06:54:28 MDT 1998",
url = "http://www.acm.org:80/pubs/citations/journals/jacm/1998-45-2/p246-karger/",
abstract = "We consider the problem of coloring {\em
k\/}-colorable graphs with the fewest possible colors.
We present a randomized polynomial time algorithm that
colors a 3-colorable graph on $n$ vertices with
min($O(\&Dgr;1/3 log1/2 \&Dgr; \log n), O(n 1/4 \log
1/2 n)$) colors where \&Dgr; is the maximum degree of
any vertex. Besides giving the best known approximation
ratio in terms of $n$, this marks the first nontrivial
approximation result as a function of the maximum
degree \&Dgr;. This result can be generalized to {\em
k\/}-colorable graphs to obtain a coloring using
min($O(\&Dgr;1-2/{\em k\/} log1/2 \&Dgr; \log n), O(n
1-;3/({\em k\/}+1) \log 1/2 n)$) colors. Our results
are inspired by the recent work of Goemans and
Williamson who used an algorithm for {\em 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 Lov{\'a}sz [theta]-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 [theta]-function.",
acknowledgement = ack-nhfb,
keywords = "algorithms; theory",
subject = "{\bf G.2.2} Mathematics of Computing, DISCRETE
MATHEMATICS, Graph Theory. {\bf F.2.2} Theory of
Computation, ANALYSIS OF ALGORITHMS AND PROBLEM
COMPLEXITY, Nonnumerical Algorithms and Problems. {\bf
G.2.1} Mathematics of Computing, DISCRETE MATHEMATICS,
Combinatorics.",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@InProceedings{Karger:1998:FMF,
author = "David R. Karger and Matthew S. Levine",
title = "Finding maximum flows in undirected graphs seems
easier than bipartite matching",
editor = "{ACM}",
booktitle = "Proceedings of the thirtieth annual {ACM} Symposium on
Theory of Computing: Dallas, Texas, May 23--26, 1998",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1998",
ISBN = "0-89791-962-9",
pages = "69--78",
year = "1998",
bibdate = "Wed Apr 4 18:53:20 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/276698/p69-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/276698/p69-karger/p69-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of the proceedings of many conferences (stoc99):
@InProceedings{Karger:1999:RAG,
author = "David R. Karger and Philip Klein and Cliff Stein and
Mikkel Thorup and Neal E. Young",
title = "Rounding algorithms for a geometric embedding of
minimum multiway cut",
editor = "{ACM}",
booktitle = "Proceedings of the thirty-first annual {ACM} Symposium
on Theory of Computing: Atlanta, Georgia, May 1--4,
1999",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1999",
ISBN = "1-58113-067-8",
pages = "668--678",
year = "1999",
bibdate = "Wed Apr 4 18:53:21 MDT 2001",
url = "http://www.acm.org/pubs/citations/proceedings/stoc/301250/p668-karger/;
http://www.acm.org/pubs/articles/proceedings/stoc/301250/p668-karger/p668-karger.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@Article{Karger:1999:WCC,
author = "David Karger and Alex Sherman and Andy Berkheimer and
Bill Bogstad and Rizwan Dhanidina and Ken Iwamoto and
Brian Kim and Luke Matkins and Yoav Yerushalmi",
title = "{Web} caching with consistent hashing",
journal = "Computer Networks (Amsterdam, Netherlands: 1999)",
volume = "31",
number = "11--16",
pages = "1203--1213",
day = "17",
month = may,
year = "1999",
coden = "????",
ISSN = "1389-1286",
bibdate = "Fri Sep 24 19:43:29 MDT 1999",
url = "http://www.elsevier.com/cas/tree/store/comnet/sub/1999/31/11-16/2181.pdf",
acknowledgement = ack-nhfb,
}
From Bibliography of "Journal of Parallel and Distributed Computing":
@Article{Karger:2000:MCN,
author = "David R. Karger",
title = "Minimum cuts in near-linear time",
journal = "Journal of the ACM",
volume = "47",
number = "1",
pages = "46--76",
month = jan,
year = "2000",
coden = "JACOAH",
ISSN = "0004-5411",
bibdate = "Fri Apr 28 17:49:18 MDT 2000",
url = "http://www.acm.org/pubs/citations/journals/jacm/2000-47-1/p46-karger/",
abstract = "We significantly improve known time bounds for solving
the minimum cut problem on undirected graphs. We use a
``semiduality'' between minimum cuts and maximum
spanning tree packings combined with our previously
developed random sampling techniques. We give a
randomized (Monte Carlo) algorithm that finds a minimum
cut in an $m$-edge, $n$-vertex graph with high
probability in $O(m \log3 n)$ time. We also give a
simpler randomized algorithm that finds all minimum
cuts with high probability in $O(m \log3 n)$ time.
This variant has an optimal RNC parallelization. Both
variants improve on the previous best time bound of
$O(n2 \log3 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.",
acknowledgement = ack-nhfb,
keywords = "Monte Carlo algorithm; connectivity; min-cut;
optimization; tree packing",
subject = "Data --- Data Structures (E.1); Theory of Computation
--- Analysis of Algorithms and Problem Complexity ---
Nonnumerical Algorithms and Problems (F.2.2);
Mathematics of Computing --- Discrete Mathematics ---
Combinatorics (G.2.1); Mathematics of Computing ---
Discrete Mathematics --- Graph Theory (G.2.2);
Mathematics of Computing --- Probability and Statistics
(G.3); General Terms: Algorithms, Theory",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@Article{Karger:2000:RFP,
author = "David R. Karger",
title = "A Randomized Fully Polynomial Time Approximation
Scheme for the All-Terminal Network Reliability
Problem",
journal = "SIAM Journal on Computing",
volume = "29",
number = "2",
pages = "492--514",
month = apr,
year = "2000",
coden = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
bibdate = "Sat Jan 22 13:21:36 MST 2000",
url = "http://epubs.siam.org/sam-bin/dbq/article/29834",
acknowledgement = ack-nhfb,
}
From Bibliography of "Workshop on Algorithms and Data Structures":
@Article{Karger:2001:RFP,
author = "David R. Karger",
title = "A Randomized Fully Polynomial Time Approximation
Scheme for the All-Terminal Network Reliability
Problem",
journal = "SIAM Review",
volume = "43",
number = "3",
pages = "499--522",
month = sep,
year = "2001",
coden = "SIREAD",
ISSN = "0036-1445 (print), 1095-7200 (electronic)",
bibdate = "Mon Feb 25 18:49:59 MST 2002",
url = "http://epubs.siam.org/sam-bin/dbq/article/38714",
acknowledgement = ack-nhfb,
}
From Bibliography of "ACM Symposium on Theory of Computing":
@InProceedings{MOBICOM00*120,
author = "Jinyang Li and John Jannotti and Douglas S. J. De
Couto and David R. Karger and Robert Morris",
title = "A Scalable Location Service for Geographic Ad Hoc
Routing",
pages = "120--130",
booktitle = "Proceedings of the 6th Annual International Conference
on Mobile Computing and Networking ({MOBICOM}-00)",
month = aug # "~6--11",
publisher = "ACM Press",
address = "N. Y.",
year = "2000",
}
From Bibliography of "Journal of Computer and System Sciences":
@Article{SICOMP::KargerM1997,
title = "An {$\mathcal{NC}$} Algorithm for Minimum Cuts",
author = "David R. Karger and Rajeev Motwani",
pages = "255--272",
journal = "SIAM Journal on Computing",
month = jan,
year = "1997",
volume = "26",
number = "1",
preliminary = "stoc::KargerM1994:497",
siam-key = "27308",
references = "\cite{STOC::AjtaiKS1987} \cite{FOCS::BellareGG1990}
\cite{SICOMP::CheriyanKT1993} \cite{JCOMP::ChorG1989}
\cite{FOCS::CohenW1989} \cite{JCSS::GabberG1981}
\cite{TCS::GoldschlagerSS1982} \cite{SODA::HaoO1992}
\cite{FOCS::ImpagliazzoZ1989} \cite{IPL::IsraeliS1986}
\cite{SODA::Karger1993} \cite{SODA::Karger1994}
\cite{STOC::Karger1995} \cite{STOC::KargerM1994}
\cite{STOC::KargerS1993} \cite{SICOMP::Luby1986}
\cite{SODA::Matula1993}",
}
From Bibliography of publications on the HP/Intel IA-64 architecture:
@InProceedings{SIGCOMM01*149,
author = "Ion Stoica and Robert Morris and David Karger and
Frans Kaashoek and Hari Balakrishnan",
title = "Chord: {A} Scalable {Peer-To-Peer} Lookup Service for
Internet Applications",
pages = "149--160",
ISSN = "0146-4833",
editor = "Roch Guerin",
booktitle = "Proceedings of the {ACM} {SIGCOMM} 2001 Conference
({SIGCOMM}-01)",
month = aug # " ~27--31",
series = "Computer Communication Review",
volume = "31, 4",
publisher = "ACM Press",
address = "New York",
year = "2001",
}
From Bibliography of "SIAM Journal on Computing":
@InProceedings{SODA01*392,
author = "David Karger and Nathan Srebro",
title = "Learning Markov Networks: Maximum Bounded {Tree-Width}
Graphs",
pages = "392--401",
booktitle = "Proceedings of the Twelfth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms ({SODA}-01)",
month = jan # " ~7--9",
publisher = "ACM Press",
address = "New York",
year = "2001",
}
From Bibliography of the proceedings of many conferences (sosp01):
@InProceedings{SODA01*577,
author = "Daniel W. Engels and Jon Feldman and David R. Karger
and Matthias Ruhl",
title = "Parallel Processor Scheduling with Delay Constraints",
pages = "577--585",
booktitle = "Proceedings of the Twelfth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms ({SODA}-01)",
month = jan # " ~7--9",
publisher = "ACM Press",
address = "New York",
year = "2001",
}
From Bibliography on Computational Intelligence and Efficient Algorithms:
@InProceedings{SODA98*500,
author = "Andr{\'a}s A. Bencz{\'u}r and David R. Karger",
title = "Augmenting Undirected Edge Connectivity in
{{\~{O}}{(n{\raisebox}{1ex}{2})}} Time",
pages = "500--509",
ISBN = "0-89871-410-9",
booktitle = "Proceedings of the 9th Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms ({SODA}-98)",
month = jan # "~25--27",
publisher = "ACM Press",
address = "New York",
year = "1998",
}
From Bibliography of the proceedings of many conferences (sigcomm01):
@InProceedings{SODA::AroraGKKW1998,
title = "A Polynomial-Time Approximation Scheme for Weighted
Planar Graph~{TSP}",
author = "Sanjeev Arora and Michelangelo Grigni and David Karger
and Philip Klein and Andrzej Woloszyn",
pages = "33--41",
booktitle = "Proceedings of the Ninth Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
month = "25--27 " # jan,
year = "1998",
address = "San Francisco, California",
references = "\cite{FOCS::Arora1996} \cite{FOCS::Arora1997}
\cite{JACM::Baker1994} \cite{FOCS::GrigniKP1995}
\cite{SICOMP::LiptonT1980} \cite{JCSS::Miller1986}
\cite{SICOMP::Mitchell1998}
\cite{JCSS::PapadimitriouY1991}",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@InProceedings{SODA::BenczurK1998,
title = "Augmenting Undirected Edge Connectivity in
{$\tilde{O}(n2)$} Time",
author = "Andr{\'a}s Bencz{\'u}r and David R. Karger",
pages = "500--509",
booktitle = "Proceedings of the Ninth Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
month = "25--27 " # jan,
year = "1998",
address = "San Francisco, California",
references = "\cite{STOC::Benczur1994} \cite{FOCS::Benczur1995}
\cite{STOC::BenczurK1996} \cite{SICOMP::BerkmanV1993}
\cite{FOCS::Frank1990} \cite{FOCS::Gabow1991}
\cite{STOC::Gabow1994} \cite{SODA::GoemansGPSTW1994}
\cite{SODA::HaoO1992} \cite{SODA::Karger1993}
\cite{STOC::Karger1996} \cite{STOC::KargerS1993}
\cite{JACM::KargerS1996} \cite{STOC::NagamochiI1996}
\cite{FOCS::NaorGM1990} \cite{SICOMP::SchieberV1988}
\cite{JCSS::WatanabeN1987}",
}
From Web caching bibliography:
@InProceedings{SODA::ChekuriGKLS1997,
title = "Experimental Study of Minimum Cut Algorithms",
author = "Chandra S. Chekuri and Andrew V. Goldberg and David R.
Karger and Matthew S. Levine and Cliff Stein",
pages = "324--333",
booktitle = "Proceedings of the Eighth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms",
month = "5--7 " # jan,
year = "1997",
address = "New Orleans, Louisiana",
references = "\cite{SICOMP::AhujaOT1989} \cite{FOCS::CheriyanH1989}
\cite{JCSS::Gabow1995} \cite{JACM::GoldbergT1988}
\cite{SODA::HaoO1992} \cite{JALGO::HaoO1994}
\cite{STOC::Karger1995} \cite{STOC::Karger1996}
\cite{STOC::KargerS1993} \cite{JALGO::KingRT1994}
\cite{FOCS::PlotkinST1991}",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{SODA::Karger1993,
title = "Global Min-cuts in {$\mathcal{RNC}$}, and Other
Ramifications of a Simple Min-Cut Algorithm",
author = "David R. Karger",
pages = "21--30",
booktitle = "Proceedings of the Fourth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms",
month = "25--27 " # jan,
year = "1993",
address = "Austin, Texas",
}
From Bibliography of the proceedings of many conferences (soda93):
@InProceedings{SODA::Karger1994,
title = "Using Randomized Sparsification to Approximate Minimum
Cuts",
author = "David R. Karger",
pages = "424--432",
booktitle = "Proceedings of the Fifth Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
month = "23--25 " # jan,
year = "1994",
address = "Arlington, Virginia",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@InProceedings{SODA::Karger1998,
title = "Better Random Sampling Algorithms for Flows in
Undirected Graphs",
author = "David R. Karger",
pages = "490--499",
booktitle = "Proceedings of the Ninth Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
month = "25--27 " # jan,
year = "1998",
address = "San Francisco, California",
references = "\cite{STOC::BenczurK1996} \cite{FOCS::GoldbergR1997}
\cite{FOCS::GoldbergR1997} \cite{STOC::Karger1996}
\cite{STOC::karger1997} \cite{ALGOR::NagamochiI1992}",
}
From Bibliography of the proceedings of many conferences (sigir92):
@InProceedings{SODA::KargerT1997,
title = "Implementing a Fully Polynomial Time Approximation
Scheme for All Terminal Network Reliability",
author = "David R. Karger and Ray P. Tai",
pages = "334--343",
booktitle = "Proceedings of the Eighth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms",
month = "5--7 " # jan,
year = "1997",
address = "New Orleans, Louisiana",
references = "\cite{SODA::ChekuriGKLS1997} \cite{STOC::Karger1994}
\cite{STOC::Karger1995} \cite{JCOMP::KarpL1985}
\cite{JALGO::KarpLM1989} \cite{SICOMP::KargerM1997}
\cite{STOC::KargerS1993} \cite{JACM::KargerS1996}
\cite{SICOMP::ProvanB1983} \cite{SICOMP::Valiant1979}",
}
From Bibliography of "ACM-SIAM Symposium on Discrete Algorithms":
@InProceedings{SOSP01*202,
author = "Frank Dabek and M. Frans Kaashoek and David Karger and
Robert Morris and Ion Stoica",
title = "{Wide-Area} Cooperative Storage with {CFS}",
pages = "202--215",
ISSN = "0163-5980",
editor = "Greg Ganger",
booktitle = "Proceedings of the 18th {ACM} Symposium on Operating
Systems Principles ({SOSP}-01)",
month = oct # " ~21--24",
series = "ACM SIGOPS Operating Systems Review",
volume = "35, 5",
publisher = "ACM Press",
address = "New York",
year = "2001",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@TechReport{STAN//CS-TR-95-1541,
type = "Thesi",
number = "CS-TR-95-1541",
title = "Random Sampling in Graph Optimization Problems",
month = feb,
notes = "[Adminitrivia V1/Prg/19950207]",
pages = "250",
year = "1995",
bibdate = "February 07, 1995",
author = "David R. Karger",
abstract = "The representative random sample is a central concept
of statistics. It is often possible to gather a great
deal of information about a large population by
examining a small sample randomly drawn from it. This
approach has obvious advantages in reducing the
investigator's work, both in gathering and in analyzing
the data. We apply the concept of a representative
sample to combinatorial optimization. Our focus is
optimization problems on undirected graphs. Highlights
of our results include: The first (randomized) linear
time minimum spanning tree algorithm; A (randomized)
minimum cut algorithm with running time roughly O(n2)
as compared to previous roughly O(n3) time bounds, as
well as the first algorithm for finding all
approximately minimal cuts and multiway cuts; An
efficient parallelization of the minimum cut algorithm,
providing the first parallel (RNC) algorithm for
minimum cuts; A derandomization finding minimum cut in
NC; Provably accurate approximations to network
reliability; Very fast approximation algorithms for
minimum cuts, s-t minimum cuts, and maximum flows;
Significantly improved polynomial-time approximation
bounds for network design problems; For coloring
3-colorable graphs, improvements in the approximation
bounds from O(n^{3/8}) to O(n^{1/4}); An analysis of
random sampling in Matroids.",
institution = "Stanford University, Department of Computer Science",
}
From Bibliography of the Journal of the ACM:
@InProceedings{STOC96*47,
author = "Andr{\'a}s A. Bencz{\'u}r and David R. Karger",
title = "Approximating s-t Minimum Cuts in {O}(n{$^{2}$})
time",
pages = "47--55",
booktitle = "Proceedings of The Twenty-Eighth Annual {ACM}
Symposium On The Theory Of Computing ({STOC} '96)",
ISBN = "0-89791-785-5",
month = may,
publisher = "ACM Press",
address = "New York, USA",
year = "1996",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{STOC98*69,
author = "David R. Karger and Matthew S. Levine",
title = "Finding Maximum Flows in Simple Undirected Graphs is
Easier Than Bipartite Matching",
pages = "69--78",
ISBN = "0-89791-962-9",
booktitle = "Proceedings of the 30th Annual {ACM} Symposium on
Theory of Computing ({STOC}-98)",
month = may # "~23--26",
publisher = "ACM Press",
address = "New York",
year = "1998",
}
From Richard Webber's Research Bibliography:
@InProceedings{STOC99*668,
author = "David R. Karger and Philip Klein and Cliff Stein and
Mikkel Thorup and Neal E. Young",
title = "Rounding Algorithms for a Geometric Embedding of
Minimum Multiway Cut",
pages = "668--678",
booktitle = "Proceedings of the Thirty-First Annual {ACM} Symposium
on Theory of Computing ({STOC}'99)",
ISBN = "1-58113-067-8",
month = may,
publisher = "Association for Computing Machinery",
address = "New York",
year = "1999",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{STOC::AroraKK1995,
title = "Polynomial Time Approximation Schemes for Dense
Instances of {${\cal NP}$}-Hard Problems",
author = "Sanjeev Arora and David Karger and Marek Karpinski",
pages = "284--293",
booktitle = "Proceedings of the Twenty-Seventh Annual {ACM}
Symposium on the Theory of Computing",
month = "29 " # may # "--1 " # jun,
year = "1995",
address = "Las Vegas, Nevada",
references = "\cite{FOCS::AlonFW1994} \cite{FOCS::AroraLMSS1992}
\cite{FOCS::AroraS1992} \cite{FOCS::BuiCLS1984}
\cite{FOCS::BellareGG1990} \cite{FOCS::BellareR1994}
\cite{STOC::DahlhausJPSY1992}
\cite{FOCS::FeigeGLSS1991} \cite{FOCS::Gillman1993}
\cite{STOC::GoemansW1994} \cite{JACM::IbarraK1975}
\cite{FOCS::JerrumS1993} \cite{FOCS::KarmarkarK1982}
\cite{FOCS::KortsarzP1993} \cite{FOCS::LeightonR1988}
\cite{STOC::LundY1993}
\cite{STOC::PapadimitriouY1988}",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{STOC::BenczurK1996,
title = "Approximating $s$-$t$ Minimum Cuts in
{$\tilde{O}(n2)$} time",
author = "Andr{\'a}s A. Bencz{\'u}r and David R. Karger",
pages = "47--55",
booktitle = "Proceedings of the Twenty-Eighth Annual {ACM}
Symposium on the Theory of Computing",
month = "22--24 " # may,
year = "1996",
address = "Philadelphia, Pennsylvania",
references = "\cite{SICOMP::DixonRT1992} \cite{JCSS::Gabow1995}
\cite{STOC::Gabow1991} \cite{JACM::GoldbergT1988}
\cite{STOC::Karger1994} \cite{SODA::Karger1994}
\cite{STOC::KleinST1990} \cite{ALGOR::NagamochiI1992}",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@InProceedings{STOC::Karger1994,
title = "Random Sampling in Cut, Flow, and Network Design
Problems",
author = "David R. Karger",
pages = "648--657",
booktitle = "Proceedings of the Twenty-Sixth Annual {ACM} Symposium
on the Theory of Computing",
month = "23--25 " # may,
year = "1994",
address = "Montr\'eal, Qu\'ebec, Canada",
references = "\cite{FOCS::EppsteinGIN1992} \cite{STOC::Gabow1991}
\cite{FOCS::Gabow1991} \cite{FOCS::Gabow1993}
\cite{FOCS::Karger1993} \cite{STOC::KargerS1993}
\cite{STOC::KhullerV1992} \cite{STOC::KleinST1990}
\cite{STOC::KleinT1994} \cite{FOCS::LeightonR1988}
\cite{STOC::WilliamsonGMV1993}",
}
From Bibliography of the journal Information Processing Letters:
@InProceedings{STOC::Karger1995,
title = "A Randomized Fully Polynomial Time Approximation
Scheme for the All Terminal Network Reliability
Problem",
author = "David R. Karger",
pages = "11--17",
booktitle = "Proceedings of the Twenty-Seventh Annual {ACM}
Symposium on the Theory of Computing",
month = "29 " # may # "--1 " # jun,
year = "1995",
address = "Las Vegas, Nevada",
references = "\cite{FOCS::AlonFW1994} \cite{JACM::DyerFK1991}
\cite{FOCS::Kannan1994} \cite{STOC::Karger1994}
\cite{STOC::KargerM1994} \cite{STOC::KargerS1993}",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{STOC::Karger1996,
title = "Minimum Cuts in Near-Linear Time",
author = "David R. Karger",
pages = "56--63",
booktitle = "Proceedings of the Twenty-Eighth Annual {ACM}
Symposium on the Theory of Computing",
month = "22--24 " # may,
year = "1996",
address = "Philadelphia, Pennsylvania",
references = "\cite{JCSS::Gabow1995} \cite{STOC::Gabow1991}
\cite{JCSS::GabowT1985} \cite{ALGOR::GabowW1992}
\cite{JALGO::HaoO1994} \cite{SODA::HaoO1992}
\cite{SODA::Karger1993} \cite{FOCS::Karger1993}
\cite{STOC::Karger1994} \cite{STOC::Karger1995}
\cite{JACM::KargerKT1995} \cite{STOC::KargerS1993}
\cite{JACM::KargerS00} \cite{ALGOR::NagamochiI1992}
\cite{FOCS::PlotkinST1991} \cite{JCSS::SleatorT1983}
\cite{SICOMP::SchieberV1988}",
}
From Bibliography of the Journal of the ACM:
@InProceedings{STOC::Karger1997,
title = "Using Random Sampling to Find Maximum Flows in
Uncapacitated Undirected Graphs",
author = "David R. Karger",
pages = "240--249",
booktitle = "Proceedings of the Twenty-Ninth Annual {ACM} Symposium
on Theory of Computing",
month = "4--6 " # may,
year = "1997",
address = "El Paso, Texas",
references = "\cite{STOC::AlonST1990} \cite{STOC::BenczurK1996}
\cite{JALGO::GilbertHT1984} \cite{SICOMP::GabowT1989}
\cite{STOC::HenzingerK1995} \cite{STOC::Karger1994}
\cite{STOC::Karger1995} \cite{STOC::KleinPR1993}",
}
From Bibliography of "ACM Symposium on Theory of Computing":
@InProceedings{STOC::KargerLLLLP1997,
title = "Consistent Hashing and Random Trees: Distributed
Caching Protocols for Relieving Hot Spots on the {World
Wide Web}",
author = "David Karger and Eric Lehman and Tom Leighton and
Matthew Levine and Daniel Lewin and Rina Panigrahy",
pages = "654--663",
booktitle = "Proceedings of the Twenty-Ninth Annual {ACM} Symposium
on Theory of Computing",
month = "4--6 " # may,
year = "1997",
address = "El Paso, Texas",
references = "\cite{FOCS::PlaxtonR1996} \cite{JACM::Rabin1989}
\cite{SODA::SchmidtSS1993}",
}
From Bibliography on Hashing:
@InProceedings{STOC::KargerM1994,
title = "Derandomization through Approximation: An {$\cal{NC}$}
Algorithm for Minimum Cuts",
author = "David R. Karger and Rajeev Motwani",
pages = "497--506",
booktitle = "Proceedings of the Twenty-Sixth Annual {ACM} Symposium
on the Theory of Computing",
month = "23--25 " # may,
year = "1994",
address = "Montr\'eal, Qu\'ebec, Canada",
references = "\cite{STOC::AggarwalA1987} \cite{STOC::AjtaiKS1987}
\cite{FOCS::BellareGG1990} \cite{FOCS::CohenW1989}
\cite{FOCS::ImpagliazzoZ1989}
\cite{STOC::KargerS1993}",
}
From Bibliography of the Journal of Parallel and Distributed Computing:
@InProceedings{STOC::KargerP1995,
title = "Adding Multiple Cost Constraints to Combinatorial
Optimization Problems, with Applications to
Multicommodity Flows",
author = "David Karger and Serge Plotkin",
pages = "18--25",
booktitle = "Proceedings of the Twenty-Seventh Annual {ACM}
Symposium on the Theory of Computing",
month = "29 " # may # "--1 " # jun,
year = "1995",
address = "Las Vegas, Nevada",
references = "\cite{STOC::AwerbuchL1994} \cite{STOC::GoldbergT1987}
\cite{STOC::KapoorV1986} \cite{STOC::Karp1991}
\cite{FOCS::LeightonR1988} \cite{FOCS::Vaidya1989}",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{WADS::KargerMR1993,
title = "On Approximating the Longest Path in a Graph
(Preliminary Version)",
author = "David R. Karger and Rajeev Motwani and G. D. S.
Ramkumar",
booktitle = "Algorithms and Data Structures, Third Workshop",
editor = "Frank K. H. A. Dehne and J{\"o}rg-R{\"u}diger Sack and
Nicola Santoro and Sue Whitesides",
address = "Montr{\'e}al, Canada",
month = "11--13~" # aug,
year = "1993",
series = "Lecture Notes in Computer Science",
volume = "709",
publisher = "Springer",
ISBN = "ISBN 3-540-57155-8",
pages = "421--432",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@Article{Young:1997:NIB,
author = "Cliff Young and David S. Johnson and David R. Karger
and Michael D. Smith",
title = "Near-optimal Intraprocedural Branch Alignment",
journal = "ACM SIG{\-}PLAN Notices",
volume = "32",
number = "5",
pages = "183--193",
month = may,
year = "1997",
coden = "SINODQ",
ISBN = "0-89791-907-6",
ISSN = "0362-1340",
bibdate = "Thu May 13 12:37:28 MDT 1999",
url = "http://www.acm.org:80/pubs/citations/proceedings/pldi/258915/p183-young/",
acknowledgement = ack-nhfb,
annote = "Published as part of the Proceedings of PLDI'97.",
keywords = "algorithms; design; experimentation; languages;
measurement; performance; standardization; theory",
subject = "{\bf C.1.2} Computer Systems Organization, PROCESSOR
ARCHITECTURES, Multiple Data Stream Architectures
(Multiprocessors), Pipeline processors**. {\bf D.3.4}
Software, PROGRAMMING LANGUAGES, Processors, Compilers.
{\bf G.1.6} Mathematics of Computing, NUMERICAL
ANALYSIS, Optimization. {\bf K.6.2} Computing Milieux,
MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS,
Installation Management, Benchmarks. {\bf G.4}
Mathematics of Computing, MATHEMATICAL SOFTWARE,
Algorithm design and analysis.",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{arora95:_polyn_time_approx_schem_dense,
author = "Sanjeev Arora and David R. Karger and Marek
Karpinski",
title = "Polynomial Time Approximation Schemes for Dense
Instances of {\NP}-Hard Problems",
booktitle = "Proceedings of the Twenty-Seventh Annual ACM Symposium
on Theory of Computing",
pages = "284--293",
year = "1995",
address = "Las Vegas NE",
organization = "Association for Computing Machinery",
language = "english",
note = "Final version to appear in Journal of Computer and
System Sciences",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{cutt93,
author = "Douglass R. Cutting and David Karger and Jan
Pedersen",
title = "Constant interaction-time Scatter/Gather browsing of
very large document collections",
booktitle = "Proceedings of the Sixteenth Annual International ACM
SIGIR Conference on Research and Development in
Information Retrieval",
year = "1993",
pages = "126--135",
entered-by = "Andreas Paepcke",
keywords = "Scatter/Gather",
comments = "~",
}
From Bibliography of papers presented at the biennial IEEE Hot Topics in Operating Systems workshops:
@InProceedings{karg99a,
author = "David Karger and Alex Sherman and Andy Berkheimer and
Bill Bogstad and Rizwan Dhanidina and Ken Iwamoto and
Brian Kim and Luke Matkins and Yoav Yerushalmi",
title = "Web Caching with Consistent Hashing",
booktitle = "Proceedings of the Eighth International World-Wide Web
Conference",
year = "1999",
entered-by = "Rebecca Wesley",
keywords = "load balancing",
comments = "A key performance measure for the World Wide Web is
the speed with which content is served to users. As
traffic on the Web increases, users are faced with
increasing delays and failures in data delivery. Web
caching is one of the key strategies that has been
explored to improve performance. An important issue in
many caching systems is how to decide what is cached
where at any given time. Solutions have included
multicast queries and directory schemes. In this paper,
we offer a new Web caching strategy based on consistent
hashing. Consistent hashing provides an alternative to
multicast and directory schemes, and has several other
advantages in load balancing and fault tolerance. Its
performance was analyzed theoretically in previous
work: in this paper we describe the implementation of a
consistent-hashing-based system and experiments that
support our thesis that it can provide performance
improvements.",
}
From Bibliography of the proceedings volumes of the annual ACM Symposia on the Theory of Computing (STOC):
@InProceedings{karger93:_algor_minim_cuts,
author = "David R. Karger and Clifford Stein",
title = "An {$\TildeOmikron\left(n2\right)$} Algorithm for
Minimum Cuts",
booktitle = "Proceedings of the Twenty-Fifth Annual ACM Symposium
on Theory of Computing",
pages = "757--765",
year = "1993",
address = "San Diego CA",
month = "16--18 " # may,
organization = "Association for Computing Machinery",
language = "english",
}
From Bibliography of the Journal of the ACM:
@Article{karger97:_nc_algor_minim_cuts,
author = "David R. Karger and Rajeev Motwani",
title = "An {\NC} Algorithm for Minimum Cuts",
journal = "SIAM Journal on Computing",
year = "1997",
volume = "26",
number = "1",
pages = "255--272",
month = feb,
language = "english",
}
From Bibliography of the SIAM Journal on Computing:
@Article{karger99b,
author = "David Karger and Alex Sherman and Andy Berkheimer and
Bill Bogstad and Rizwan Dhanidina and Ken Iwamoto and
Brian Kim and Luke Matkins and Yoav Yerushalmi",
title = "Web Caching with Consistent Hashing",
journal = "Computer Networks and ISDN Systems",
year = "1999",
volume = "31",
number = "11-16",
pages = "1203--1213",
month = may,
note = "\url{http://www.elsevier.nl/cas/tree/store/
comnet/sub/1999/31/11-16/2181.pdf}",
}
From Bibliography of the technical reports of the International Computer Science Institute ICSI:
@TechReport{ncstrl.dartmouthcs//TR94-213,
type = "Technical Report (paper)",
number = "TR94-213",
title = "Job Scheduling in Rings",
month = jan,
contact = "",
url = "ftp://ftp.cs.dartmouth.edu/TR/TR94-213.ps.Z",
revision = "1",
year = "1994",
bibdate = "January 20, 1995",
author = "Perry Fizzano and Clifford Stein and David R. Karger
and Joel Wein",
abstract = "We give distributed approximation algorithms for job
scheduling in a ring architecture. In contrast to
almost all other parallel scheduling models, the model
we consider captures the influence of the underlying
communications network by specifying that task
migration from one processor to another takes time
proportional to the distance between those two
processors in the network. As a result, our algorithms
must balance both computational load and communication
time. The algorithms are simple, require no global
control, and work in a variety of settings. All come
with small constant-factor approximation guarantees;
the basic algorithm yields schedules of length at most
4.22 times optimal. We also give a lower bound on the
performance of any distributed algorithm some results
for a simple capacitated case, and the results of
simulation experiments, which give better results than
our worst-case analysis.",
institution = "Dartmouth College, Computer Science",
}
From The HCI Bibliography (IR93):
@TechReport{ncstrl.dartmouthcs//TR94-229,
type = "Technical Report (paper)",
number = "TR94-229",
title = "A New Approach to the Minumum Cut Problem",
month = jan,
contact = "",
revision = "1",
year = "1994",
bibdate = "January 20, 1995",
author = "David R. Karger and Clifford Stein",
institution = "Dartmouth College, Computer Science",
}
From Bibliography of Technical Reports: Dartmouth College:
@TechReport{ncstrl.unibonn_cs//85119-CS,
type = "Technical Report",
number = "85119-CS",
institution = "University of Bonn, Department of Computer Science",
title = "Polynomial Time Approximation Schemes for Dense
Instances of {NP}-Hard Problems",
month = sep,
year = "1994",
bibdate = "October 28, 97",
author = "Sanjeev Arora and David Karger and Marek Karpinski",
}
From Bibliography of the "Journal of the ACM":
@TechReport{ncstrl.unibonn_cs//85195-CS,
type = "Technical Report",
number = "85195-CS",
institution = "University of Bonn, Department of Computer Science",
title = "Polynomial Time Approximation Schemes for Dense
Instances of {NP}-Hard Problems",
year = "1998",
url = "ftp://theory.cs.uni-bonn.de/pub/reports/cs-reports/1998/85195-cs.ps.gz",
author = "David Karger Sanjeev Arora and Marek Karpinski",
}
From Annotated Bibliography of Digital Library Related Sources:
@InProceedings{pldi97*183,
author = "Cliff Young and David S. Johnson and David R. Karger
and Michael D. Smith",
title = "Near-optimal Intraprocedural Branch Alignment",
pages = "183--193",
ISSN = "0362-1340",
booktitle = "Proceedings of the {ACM} {SIGPLAN} Conference on
Programming Language Design and Implementation
({PLDI}-97)",
month = jun # "~15--18",
series = "ACM SIGPLAN Notices",
volume = "32, 5",
publisher = "ACM Press",
address = "New York",
year = "1997",
}
From The HCI Bibliography (IR92):
@InProceedings{ref:Hearst:1995b,
author = "Marti A. Hearst and David R. Karger and Jan O.
Pedersen",
title = "Scatter/Gather as a Tool for the Navigation of
Retrieval Results",
booktitle = "Working Notes AAAI Fall Symp. AI Applications in
Knowledge Navigation",
location = "Cambridge, Massachusetts",
month = nov,
year = "1995",
gzipped-postscript-url = "ftp://parcftp.xerox.com/pub/hearst/knowlnav95.ps.gz",
}
From Richard Webber's Research Bibliography:
@InProceedings{sigir92*318,
author = "Douglas R. Culling and Jan O. Pedersen and David
Karger and John W. Tukey",
title = "Scatter/Gather: {A} Cluster-based Approach to Browsing
Large Document Collections",
pages = "318--329",
ISBN = "0-89791-524-0",
editor = "Nicholas Belkin and Peter Ingwersen and Annelise Mark
Pejtersen",
booktitle = "Proceedings of the 15th Annual International
Conference on Reasearch and Development in Information
Retrieval",
month = jun,
series = "SIGIR Forum",
publisher = "ACM Press",
address = "New York, NY, USA",
year = "1992",
}
From Bibliography of Technical Reports: Stanford University:
@InProceedings{soda93*21,
author = "David R. Karger",
title = "Global Min-cuts in {\cal{RNC}}, and Other
Ramifications of a Simple Min-Cut Algorithm",
pages = "21--30",
ISBN = "0-89871-313-7",
editor = "Mihalis {Ramachandran, Vijaya; Bentley, jon; cole,
Richard; Cunningham, William H.; Guibas, Leo; King,
Valerie; Lawler, Eugene; Lenstra, Arjen; Mulmuley,
Ketan; Sleator, Daniel D.; Yannakakis}",
booktitle = "Proceedings of the 4th Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms ({SODA} '93)",
address = "Austin, TX, USA",
month = jan,
year = "1993",
publisher = "SIAM",
}
From Bibliography of the "Journal of the ACM":
@InProceedings{soda94*132,
author = "David R. Karger and Steven J. Phillips and Eric
Torng",
title = "A Better Algorithm for an Ancient Scheduling Problem",
pages = "132--140",
ISBN = "0-89871-329-3",
editor = "Daniel D. Sleator",
booktitle = "Proceedings of the 5th Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
address = "Arlington, VA",
month = jan,
year = "1994",
publisher = "ACM Press",
}
From Bibliography of the "Journal of the ACM":
@InProceedings{soda94*424,
author = "David R. Karger",
title = "Using Randomised Sparsification to Approximate Minimum
Cuts",
pages = "424--432",
ISBN = "0-89871-329-3",
editor = "Daniel D. Sleator",
booktitle = "Proceedings of the 5th Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms",
address = "Arlington, VA",
month = jan,
year = "1994",
publisher = "ACM Press",
}
From Bibliography of the "Journal of the ACM":
@InProceedings{spaa92*373,
author = "David Karger and Noam Nisan and Michael Parnas",
title = "Fast connected components algorithms for the {EREW}
{PRAM}",
pages = "373--381",
ISBN = "0-89791-483-X / 0-89791-484-8",
booktitle = "Proceedings of the 4th Annual Symposium on Parallel
Algorithms and Architectures",
address = "San Diego, CA, USA",
month = jun,
year = "1992",
publisher = "ACM Press",
}
From Bibliography on the theory/foundations of computer science:
@InProceedings{stoc94*497,
author = "David R. Karger and Rajeev Motwani",
title = "Derandomization through approximation: An {NC}
algorithm for minimum cuts",
pages = "497--506",
ISBN = "0-89791-663-8",
booktitle = "Proceedings of the 26th Annual Symposium on the Theory
of Computing",
month = may,
publisher = "ACM Press",
address = "New York",
year = "1994",
}