2009 |
157 | EE | Max Van Kleek,
Michael S. Bernstein,
Katrina Panovich,
Gregory G. Vargas,
David R. Karger,
Monica M. C. Schraefel:
Note to self: examining personal information keeping in a lightweight note-taking tool.
CHI 2009: 1477-1480 |
156 | EE | David R. Karger,
Debmalya Panigrahi:
A near-linear time algorithm for constructing a cactus representation of minimum cuts.
SODA 2009: 246-255 |
2008 |
155 | | Evdokia Nikolova,
David R. Karger:
Route Planning under Uncertainty: The Canadian Traveller Problem.
AAAI 2008: 969-974 |
154 | EE | David R. Karger,
Jacob Scott:
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP.
APPROX-RANDOM 2008: 104-117 |
153 | EE | Vineet Sinha,
Elizabeth L. Murnane,
Scott W. Kurth,
Edy S. Liongosari,
Rob Miller,
David R. Karger:
Understanding code architectures via interactive exploration and layout of layered diagrams.
OOPSLA Companion 2008: 745-746 |
152 | EE | Vineet Sinha,
Elizabeth L. Murnane,
Scott W. Kurth,
Edy S. Liongosari,
Rob Miller,
David R. Karger:
Understanding code architectures via interactive exploration and layout of layered diagrams.
OOPSLA Companion 2008: 775-776 |
151 | EE | Aaron Bernstein,
David R. Karger:
Improved distance sensitivity oracles via random sampling.
SODA 2008: 34-43 |
150 | EE | Christopher Y. Crutchfield,
Zoran Dzunic,
Jeremy T. Fineman,
David R. Karger,
Jacob Scott:
Improved approximations for multiprocessor scheduling under uncertainty.
SPAA 2008: 246-255 |
149 | EE | Robert C. Miller,
Victoria H. Chou,
Michael S. Bernstein,
Greg Little,
Max Van Kleek,
David R. Karger,
m. c. schraefel:
Inky: a sloppy command line for the web with rich visual feedback.
UIST 2008: 131-140 |
148 | EE | Michael S. Bernstein,
Max Van Kleek,
David R. Karger,
m. c. schraefel:
Information scraps: How and why information eludes our personal information management tools.
ACM Trans. Inf. Syst. 26(4): (2008) |
147 | EE | Christopher Y. Crutchfield,
Zoran Dzunic,
Jeremy T. Fineman,
David R. Karger,
Jacob Scott:
Improved Approximations for Multiprocessor Scheduling Under Uncertainty
CoRR abs/0802.2418: (2008) |
146 | EE | Tracey Ho,
Ben Leong,
Ralf Koetter,
Muriel Médard,
Michelle Effros,
David R. Karger:
Byzantine Modification Detection in Multicast Networks With Random Network Coding.
IEEE Transactions on Information Theory 54(6): 2798-2803 (2008) |
145 | EE | David F. Huynh,
Robert C. Miller,
David R. Karger:
Potluck: Data mash-up tool for casual users.
J. Web Sem. 6(4): 274-282 (2008) |
2007 |
144 | EE | Michael S. Bernstein,
Max Van Kleek,
m. c. schraefel,
David R. Karger:
Management of personal information scraps.
CHI Extended Abstracts 2007: 2285-2290 |
143 | EE | David F. Huynh,
Robert C. Miller,
David R. Karger:
Potluck: Data Mash-Up Tool for Casual Users.
ISWC/ASWC 2007: 239-252 |
142 | EE | David F. Huynh,
Robert C. Miller,
David R. Karger:
Potluck: Semi-ontology Alignment for Casual Users.
ISWC/ASWC 2007: 903-910 |
141 | EE | David R. Karger,
Krzysztof Onak:
Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems.
SODA 2007: 1207-1216 |
140 | EE | David F. Huynh,
Robert C. Miller,
David R. Karger:
Potluck: Semi-Ontology Alignment for Casual Users.
Semantic Web Challenge 2007 |
139 | EE | Max Van Kleek,
Michael S. Bernstein,
David R. Karger,
m. c. schraefel:
Gui --- phooey!: the case for text input.
UIST 2007: 193-202 |
138 | EE | Yuan Kui Shen,
David R. Karger:
U-REST: an unsupervised record extraction system.
WWW 2007: 1347-1348 |
137 | EE | David F. Huynh,
David R. Karger,
Robert C. Miller:
Exhibit: lightweight structured data publishing.
WWW 2007: 737-746 |
136 | EE | David Huynh,
Stefano Mazzocchi,
David R. Karger:
Piggy Bank: Experience the Semantic Web inside your web browser.
J. Web Sem. 5(1): 16-27 (2007) |
135 | EE | Avrim Blum,
Shuchi Chawla,
David R. Karger,
Terran Lane,
Adam Meyerson,
Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
SIAM J. Comput. 37(2): 653-670 (2007) |
134 | EE | Joan Feigenbaum,
David R. Karger,
Vahab S. Mirrokni,
Rahul Sami:
Subjective-cost policy routing.
Theor. Comput. Sci. 378(2): 175-189 (2007) |
2006 |
133 | | Evdokia Nikolova,
Matthew Brand,
David R. Karger:
Optimal Route Planning under Uncertainty.
ICAPS 2006: 131-141 |
132 | EE | Emmanuel Pietriga,
Christian Bizer,
David R. Karger,
Ryan Lee:
Fresnel: A Browser-Independent Presentation Vocabulary for RDF.
International Semantic Web Conference 2006: 158-171 |
131 | EE | Michael Walfish,
J. D. Zamfirescu,
Hari Balakrishnan,
David R. Karger,
Scott Shenker:
Distributed Quota Enforcement for Spam Control.
NSDI 2006 |
130 | EE | Michael Walfish,
Mythili Vutukuru,
Hari Balakrishnan,
David R. Karger,
Scott Shenker:
DDoS defense by offense.
SIGCOMM 2006: 303-314 |
129 | EE | Harr Chen,
David R. Karger:
Less is more: probabilistic models for retrieving fewer relevant documents.
SIGIR 2006: 429-436 |
128 | EE | Nicholas J. A. Harvey,
David R. Karger,
Sergey Yekhanin:
The complexity of matrix completion.
SODA 2006: 1103-1111 |
127 | EE | David F. Huynh,
Robert C. Miller,
David R. Karger:
Enabling web browsers to augment web sites' filtering and sorting functionalities.
UIST 2006: 125-134 |
126 | EE | Vineet Sinha,
David R. Karger,
Rob Miller:
Relo: Helping Users Manage Context during Interactive Exploratory Visualization of Large Codebases.
VL/HCC 2006: 187-194 |
125 | EE | Siddharth Ray,
Michelle Effros,
Muriel Médard,
Ralf Koetter,
Tracey Ho,
David R. Karger,
Jinane Abounadi:
On Separation, Randomness and Linearity for Network Codes over Finite Fields
CoRR abs/cs/0603022: (2006) |
124 | EE | David R. Karger,
William Jones:
Data unification in personal information management.
Commun. ACM 49(1): 77-82 (2006) |
123 | EE | Tracey Ho,
Muriel Médard,
Ralf Koetter,
David R. Karger,
Michelle Effros,
Jun Shi,
Ben Leong:
A Random Linear Network Coding Approach to Multicast.
IEEE Transactions on Information Theory 52(10): 4413-4430 (2006) |
122 | EE | Desmond S. Lun,
Niranjan Ratnakar,
Muriel Médard,
Ralf Koetter,
David R. Karger,
Tracey Ho,
Ebad Ahmed,
Fang Zhao:
Minimum-cost multicast over coded packet networks.
IEEE Transactions on Information Theory 52(6): 2608-2623 (2006) |
121 | EE | David R. Karger,
Matthias Ruhl:
Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems.
Theory Comput. Syst. 39(6): 787-804 (2006) |
2005 |
120 | EE | Nicole Immorlica,
David R. Karger,
Evdokia Nikolova,
Rahul Sami:
First-price path auctions.
ACM Conference on Electronic Commerce 2005: 203-212 |
119 | EE | David R. Karger,
Karun Bakshi,
David Huynh,
Dennis Quan,
Vineet Sinha:
Haystack: A General-Purpose Information Management Tool for End Users Based on Semistructured Data.
CIDR 2005: 13-26 |
118 | EE | Vineet Sinha,
David R. Karger,
Rob Miller:
Relo: helping users manage context during interactive exploratory visualization of large codebases.
ETX 2005: 21-25 |
117 | EE | Austin T. Clements,
Dan R. K. Ports,
David R. Karger:
Arpeggio: Metadata Searching and Content Sharing with Chord.
IPTPS 2005: 58-68 |
116 | EE | Jeremy Stribling,
Isaac G. Councill,
Jinyang Li,
M. Frans Kaashoek,
David R. Karger,
Robert Morris,
Scott Shenker:
OverCite: A Cooperative Digital Research Library.
IPTPS 2005: 69-79 |
115 | EE | David Huynh,
Stefano Mazzocchi,
David R. Karger:
Piggy Bank: Experience the Semantic Web Inside Your Web Browser.
International Semantic Web Conference 2005: 413-430 |
114 | EE | Vineet Sinha,
Rob Miller,
David R. Karger:
Incremental exploratory visualization of relationships in large codebases for program comprehension.
OOPSLA Companion 2005: 116-117 |
113 | EE | Vineet Sinha,
Rob Miller,
David R. Karger:
Incremental exploratory visualization of relationships in large codebases for program comprehension.
OOPSLA Companion 2005: 198-199 |
112 | EE | David R. Karger,
Evdokia Nikolova:
Brief announcement: on the expected overpayment of VCG mechanisms in large networks.
PODC 2005: 126 |
111 | EE | Vineet Sinha,
David R. Karger:
Magnet: Supporting Navigation in Semistructured Data Environments.
SIGMOD Conference 2005: 97-106 |
110 | EE | Nicholas J. A. Harvey,
David R. Karger,
Kazuo Murota:
Deterministic network coding by matrix completion.
SODA 2005: 489-498 |
109 | EE | Joan Feigenbaum,
David R. Karger,
Vahab S. Mirrokni,
Rahul Sami:
Subjective-Cost Policy Routing.
WINE 2005: 174-183 |
108 | EE | Andrew Hogue,
David R. Karger:
Thresher: automating the unwrapping of semantic content from the World Wide Web.
WWW 2005: 86-95 |
107 | EE | Desmond S. Lun,
Niranjan Ratnakar,
Muriel Médard,
Ralf Koetter,
David R. Karger,
Tracey Ho,
Ebad Ahmed,
Fang Zhao:
Minimum-Cost Multicast over Coded Packet Networks
CoRR abs/cs/0503064: (2005) |
106 | EE | David R. Karger,
Muriel Médard:
Toward Using the Network as a Switch: On the Use of TDM in Linear Optical Networks.
IEEE Journal on Selected Areas in Communications 23(8): 1533-1541 (2005) |
105 | EE | Jon Feldman,
Martin J. Wainwright,
David R. Karger:
Using linear programming to Decode Binary linear codes.
IEEE Transactions on Information Theory 51(3): 954-972 (2005) |
104 | EE | David R. Karger,
Dennis Quan:
What would it mean to blog on the semantic web?
J. Web Sem. 3(2-3): 147-157 (2005) |
2004 |
103 | EE | Jaime Teevan,
Christine Alvarado,
Mark S. Ackerman,
David R. Karger:
The perfect search engine is not enough: a study of orienteering behavior in directed search.
CHI 2004: 415-422 |
102 | EE | David R. Karger,
Dennis Quan:
Collections: flexible, essential tools for information management.
CHI Extended Abstracts 2004: 1159-1162 |
101 | EE | David R. Karger,
Dennis Quan:
Haystack: a user interface for creating, browsing, and organizing arbitrary semistructured information.
CHI Extended Abstracts 2004: 777-778 |
100 | EE | David R. Karger,
Matthias Ruhl:
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems.
IPTPS 2004: 131-140 |
99 | EE | David R. Karger,
Matthias Ruhl:
Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks.
IPTPS 2004: 288-297 |
98 | EE | David R. Karger,
Dennis Quan:
What Would It Mean to Blog on the Semantic Web?
International Semantic Web Conference 2004: 214-228 |
97 | EE | Nicole Immorlica,
David R. Karger,
Maria Minkoff,
Vahab S. Mirrokni:
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems.
SODA 2004: 691-700 |
96 | EE | David R. Karger,
Matthias Ruhl:
Simple efficient load balancing algorithms for peer-to-peer systems.
SPAA 2004: 36-43 |
95 | EE | L. K. Shih,
David R. Karger:
Using urls and table layout for web classification tasks.
WWW 2004: 193-202 |
94 | EE | Jon Feldman,
David R. Karger:
Decoding turbo-like codes via linear programming.
J. Comput. Syst. Sci. 68(4): 733-752 (2004) |
93 | EE | David R. Karger,
Philip N. Klein,
Clifford Stein,
Mikkel Thorup,
Neal E. Young:
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Math. Oper. Res. 29(3): 436-461 (2004) |
2003 |
92 | EE | Jimmy J. Lin,
Dennis Quan,
Vineet Sinha,
Karun Bakshi,
David Huynh,
Boris Katz,
David R. Karger:
The role of context in question answering systems.
CHI Extended Abstracts 2003: 1006-1007 |
91 | EE | Avrim Blum,
Shuchi Chawla,
David R. Karger,
Terran Lane,
Adam Meyerson,
Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
FOCS 2003: 46-55 |
90 | | Jason D. Rennie,
Lawrence Shih,
Jaime Teevan,
David R. Karger:
Tackling the Poor Assumptions of Naive Bayes Text Classifiers.
ICML 2003: 616-623 |
89 | | Lawrence Shih,
Jason D. Rennie,
Yu-Han Chang,
David R. Karger:
Text Bundling: Statistics Based Data-Reduction.
ICML 2003: 696-703 |
88 | | Dennis Quan,
Karun Bakshi,
David Huynh,
David R. Karger:
User Interfaces for Supporting Multiple Categorization.
INTERACT 2003 |
87 | | Jimmy J. Lin,
Dennis Quan,
Vineet Sinha,
Karun Bakshi,
David Huynh,
Boris Katz,
David R. Karger:
What Makes a Good Answer? The Role of Context in Question Answering.
INTERACT 2003 |
86 | EE | Jinyang Li,
Boon Thau Loo,
Joseph M. Hellerstein,
M. Frans Kaashoek,
David R. Karger,
Robert Morris:
On the Feasibility of Peer-to-Peer Web Indexing and Search.
IPTPS 2003: 207-215 |
85 | EE | M. Frans Kaashoek,
David R. Karger:
Koorde: A Simple Degree-Optimal Distributed Hash Table.
IPTPS 2003: 98-107 |
84 | EE | David R. Karger,
Boris Katz,
Jimmy J. Lin,
Dennis Quan:
Sticky notes for the semantic web.
IUI 2003: 254-256 |
83 | EE | David Huynh,
David R. Karger,
Dennis Quan,
Vineet Sinha:
Haystack: a platform for creating, organizing and visualizing semistructured information.
IUI 2003: 323 |
82 | EE | Dennis Quan,
David Huynh,
David R. Karger:
Haystack: A Platform for Authoring End User Semantic Web Applications.
International Semantic Web Conference 2003: 738-753 |
81 | EE | Nick Feamster,
Magdalena Balazinska,
Winston Wang,
Hari Balakrishnan,
David R. Karger:
Thwarting Web Censorship with Untrusted Messenger Discovery.
Privacy Enhancing Technologies 2003: 125-140 |
80 | EE | Jaime Teevan,
David R. Karger:
Empirical development of an exponential probabilistic model for text retrieval: using textual analysis to build a better model.
SIGIR 2003: 18-25 |
79 | EE | Dennis Quan,
David Huynh,
David R. Karger,
Robert C. Miller:
User interface continuations.
UIST 2003: 145-148 |
78 | EE | Dennis Quan,
Karun Bakshi,
David R. Karger:
A Unified Abstraction for Messaging on the Semantic Web.
WWW (Posters) 2003 |
77 | EE | Vineet Sinha,
David R. Karger,
David Huynh:
Assisted Browsing for Semistructured Data.
WWW (Posters) 2003 |
76 | EE | Dennis Quan,
David Huynh,
David R. Karger:
Haystack: A Platform for Authoring End User Semantic Web Applications.
WWW (Posters) 2003 |
75 | EE | David Huynh,
Dennis Quan,
David R. Karger:
User Interaction Experience for Semantic Web Information.
WWW (Posters) 2003 |
74 | EE | Hari Balakrishnan,
M. Frans Kaashoek,
David R. Karger,
Robert Morris,
Ion Stoica:
Looking up data in P2P systems.
Commun. ACM 46(2): 43-48 (2003) |
73 | EE | Ion Stoica,
Robert Morris,
David Liben-Nowell,
David R. Karger,
M. Frans Kaashoek,
Frank Dabek,
Hari Balakrishnan:
Chord: a scalable peer-to-peer lookup protocol for internet applications.
IEEE/ACM Trans. Netw. 11(1): 17-32 (2003) |
72 | EE | Daniel W. Engels,
David R. Karger,
Stavros G. Kolliopoulos,
Sudipta Sengupta,
R. N. Uma,
Joel Wein:
Techniques for scheduling with rejection.
J. Algorithms 49(1): 175-191 (2003) |
2002 |
71 | EE | Jon Feldman,
David R. Karger:
Decoding Turbo-Like Codes via Linear Programming.
FOCS 2002: 251-260 |
70 | EE | David Liben-Nowell,
Hari Balakrishnan,
David R. Karger:
Observations on the Dynamic Evolution of Peer-to-Peer Networks.
IPTPS 2002: 22-33 |
69 | EE | David Liben-Nowell,
Hari Balakrishnan,
David R. Karger:
Analysis of the evolution of peer-to-peer systems.
PODC 2002: 233-242 |
68 | EE | Magdalena Balazinska,
Hari Balakrishnan,
David R. Karger:
INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery.
Pervasive 2002: 195-210 |
67 | EE | David R. Karger,
Matthew S. Levine:
Random sampling in residual graphs.
STOC 2002: 63-66 |
66 | EE | David R. Karger,
Matthias Ruhl:
Finding nearest neighbors in growth-restricted metrics.
STOC 2002: 741-750 |
65 | EE | David Huynh,
David R. Karger,
Dennis Quan:
Haystack: A Platform for Creating, Organizing and Visualizing Information Using RDF.
Semantic Web Workshop 2002 |
64 | EE | Nick Feamster,
Magdalena Balazinska,
Greg Harfst,
Hari Balakrishnan,
David R. Karger:
Infranet: Circumventing Web Censorship and Surveillance.
USENIX Security Symposium 2002: 247-262 |
63 | EE | David R. Karger,
Philip N. Klein,
Clifford Stein,
Mikkel Thorup,
Neal E. Young:
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
CoRR cs.DS/0205051: (2002) |
62 | EE | András A. Benczúr,
David R. Karger:
Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
CoRR cs.DS/0207078: (2002) |
2001 |
61 | EE | Frank Dabek,
Emma Brunskill,
M. Frans Kaashoek,
David R. Karger,
Robert Morris,
Ion Stoica,
Hari Balakrishnan:
Building peer-to-peer systems with Chord, a distributed lookup service.
HotOS 2001: 81-86 |
60 | EE | Ion Stoica,
Robert Morris,
David R. Karger,
M. Frans Kaashoek,
Hari Balakrishnan:
Chord: A scalable peer-to-peer lookup service for internet applications.
SIGCOMM 2001: 149-160 |
59 | EE | David R. Karger,
Nathan Srebro:
Learning Markov networks: maximum bounded tree-width graphs.
SODA 2001: 392-401 |
58 | EE | Daniel W. Engels,
Jon Feldman,
David R. Karger,
Matthias Ruhl:
Parallel processor scheduling with delay constraints.
SODA 2001: 577-585 |
57 | EE | Frank Dabek,
M. Frans Kaashoek,
David R. Karger,
Robert Morris,
Ion Stoica:
Wide-Area Cooperative Storage with CFS.
SOSP 2001: 202-215 |
56 | | Raj Iyer,
David R. Karger,
Hariharan Rahul,
Mikkel Thorup:
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms.
ACM Journal of Experimental Algorithmics 6: 4 (2001) |
2000 |
55 | | David R. Karger,
Maria Minkoff:
Building Steiner Trees with Incomplete Global Knowledge.
FOCS 2000: 613-623 |
54 | EE | Jinyang Li,
John Jannotti,
Douglas S. J. De Couto,
David R. Karger,
Robert Morris:
A scalable location service for geographic ad hoc routing.
MOBICOM 2000: 120-130 |
53 | EE | David R. Karger:
Minimum cuts in near-linear time.
J. ACM 47(1): 46-76 (2000) |
52 | | András A. Benczúr,
David R. Karger:
Augmenting Undirected Edge Connectivity in Õ(n2) Time.
J. Algorithms 37(1): 2-36 (2000) |
1999 |
51 | EE | Eytan Adar,
David R. Karger,
Lynn Andrea Stein:
Haystack: Per-User Information Environments.
CIKM 1999: 413-422 |
50 | EE | Foto N. Afrati,
Evripidis Bampis,
Chandra Chekuri,
David R. Karger,
Claire Kenyon,
Sanjeev Khanna,
Ioannis Milis,
Maurice Queyranne,
Martin Skutella,
Clifford Stein,
Maxim Sviridenko:
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
FOCS 1999: 32-44 |
49 | EE | David R. Karger,
Philip N. Klein,
Clifford Stein,
Mikkel Thorup,
Neal E. Young:
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
STOC 1999: 668-678 |
48 | EE | David R. Karger,
Alex Sherman,
Andy Berkheimer,
Bill Bogstad,
Rizwan Dhanidina,
Ken Iwamoto,
Brian Kim,
Luke Matkins,
Yoav Yerushalmi:
Web Caching with Consistent Hashing.
Computer Networks 31(11-16): 1203-1213 (1999) |
47 | | Sanjeev Arora,
David R. Karger,
Marek Karpinski:
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems.
J. Comput. Syst. Sci. 58(1): 193-210 (1999) |
46 | | David R. Karger,
Noam Nisan,
Michal Parnas:
Fast Connected Components Algorithms for the EREW PRAM.
SIAM J. Comput. 28(3): 1021-1034 (1999) |
45 | | David R. Karger:
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem.
SIAM J. Comput. 29(2): 492-514 (1999) |
1998 |
44 | EE | Daniel W. Engels,
David R. Karger,
Stavros G. Kolliopoulos,
Sudipta Sengupta,
R. N. Uma,
Joel Wein:
Techniques for Scheduling with Rejection.
ESA 1998: 490-501 |
43 | | Sanjeev Arora,
Michelangelo Grigni,
David R. Karger,
Philip N. Klein,
Andrzej Woloszyn:
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.
SODA 1998: 33-41 |
42 | | David R. Karger:
Better Random Sampling Algorithms for Flows in Undirected Graphs.
SODA 1998: 490-499 |
41 | | András A. Benczúr,
David R. Karger:
Augmenting Undirected Edge Connectivity in Õ(n²) Time.
SODA 1998: 500-509 |
40 | EE | David R. Karger,
Matthew S. Levine:
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching.
STOC 1998: 69-78 |
39 | EE | David R. Karger:
A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
CoRR cs.DS/9809012: (1998) |
38 | EE | David R. Karger:
Minimum Cuts in Near-Linear Time
CoRR cs.DS/9812007: (1998) |
37 | EE | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming
CoRR cs.DS/9812008: (1998) |
36 | EE | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming.
J. ACM 45(2): 246-265 (1998) |
35 | | David R. Karger:
Random sampling and greedy sparsification for matroid optimization problems.
Math. Program. 82: 41-81 (1998) |
1997 |
34 | | Cliff Young,
David S. Johnson,
David R. Karger,
Michael D. Smith:
Near-optimal Intraprocedural Branch Alignment.
PLDI 1997: 183-193 |
33 | | Chandra Chekuri,
Andrew V. Goldberg,
David R. Karger,
Matthew S. Levine,
Clifford Stein:
Experimental Study of Minimum Cut Algorithms.
SODA 1997: 324-333 |
32 | | David R. Karger,
Ray P. Tai:
Implementing a Fully Polynomial Time Approximation Scheme for All Terminal Network Reliability.
SODA 1997: 334-343 |
31 | EE | David R. Karger:
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs.
STOC 1997: 240-249 |
30 | EE | David R. Karger,
Eric Lehman,
Frank Thomson Leighton,
Rina Panigrahy,
Matthew S. Levine,
Daniel Lewin:
Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.
STOC 1997: 654-663 |
29 | | David R. Karger,
Rajeev Motwani,
G. D. S. Ramkumar:
On Approximating the Longest Path in a Graph.
Algorithmica 18(1): 82-98 (1997) |
28 | EE | Avrim Blum,
David R. Karger:
An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.
Inf. Process. Lett. 61(1): 49-53 (1997) |
27 | | David R. Karger,
Daphne Koller:
(De)randomized Construction of Small Sample Spaces in NC.
J. Comput. Syst. Sci. 55(3): 402-413 (1997) |
26 | | Perry Fizzano,
David R. Karger,
Clifford Stein,
Joel Wein:
Distributed Job Scheduling in Rings.
J. Parallel Distrib. Comput. 45(2): 122-133 (1997) |
25 | | David R. Karger,
Rajeev Motwani:
An NC Algorithm for Minimum Cuts.
SIAM J. Comput. 26(1): 255-272 (1997) |
1996 |
24 | EE | András A. Benczúr,
David R. Karger:
Approximating s-t Minimum Cuts in Õ(n2) Time.
STOC 1996: 47-55 |
23 | EE | David R. Karger:
Minimum Cuts in Near-Linear Time.
STOC 1996: 56-63 |
22 | EE | David R. Karger,
Clifford Stein:
A New Approach to the Minimum Cut Problem.
J. ACM 43(4): 601-640 (1996) |
21 | | David R. Karger,
Steven J. Phillips,
Eric Torng:
A Better Algorithm for an Ancient Scheduling Problem.
J. Algorithms 20(2): 400-430 (1996) |
1995 |
20 | EE | David R. Karger:
A randomized fully polynomial time approximation scheme for the all terminal network reliability problem.
STOC 1995: 11-17 |
19 | EE | David R. Karger,
Serge A. Plotkin:
Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows.
STOC 1995: 18-25 |
18 | EE | Sanjeev Arora,
David R. Karger,
Marek Karpinski:
Polynomial time approximation schemes for dense instances of NP-hard problems.
STOC 1995: 284-293 |
17 | EE | Charles J. Alpert,
T. C. Hu,
Dennis J.-H. Huang,
Andrew B. Kahng,
David R. Karger:
Prim-Dijkstra tradeoffs for improved performance-driven routing tree design.
IEEE Trans. on CAD of Integrated Circuits and Systems 14(7): 890-896 (1995) |
16 | EE | David R. Karger,
Philip N. Klein,
Robert Endre Tarjan:
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.
J. ACM 42(2): 321-328 (1995) |
1994 |
15 | | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming
FOCS 1994: 2-13 |
14 | | David R. Karger,
Daphne Koller:
(De)randomized Construction of Small Sample Spaces in \calNC
FOCS 1994: 252-263 |
13 | | David R. Karger,
Steven J. Phillips,
Eric Torng:
A Better Algorithm for an Ancient Scheduling Problem.
SODA 1994: 132-140 |
12 | | David R. Karger:
Using Randomized Sparsification to Approximate Minimum Cuts.
SODA 1994: 424-432 |
11 | EE | Perry Fizzano,
David R. Karger,
Clifford Stein,
Joel Wein:
Job Scheduling in Rings.
SPAA 1994: 210-219 |
10 | EE | David R. Karger:
Random sampling in cut, flow, and network design problems.
STOC 1994: 648-657 |
1993 |
9 | | David R. Karger:
Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees
FOCS 1993: 84-93 |
8 | EE | Douglas R. Cutting,
David R. Karger,
Jan O. Pedersen:
Constant Interaction-Time Scatter/Gather Browsing of Very Large Document Collections.
SIGIR 1993: 126-134 |
7 | | David R. Karger:
Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm.
SODA 1993: 21-30 |
6 | EE | David R. Karger,
Clifford Stein:
An O~(n2) algorithm for minimum cuts.
STOC 1993: 757-765 |
5 | | David R. Karger,
Rajeev Motwani,
G. D. S. Ramkumar:
On Approximating the Longest Path in a Graph (Preliminary Version).
WADS 1993: 421-432 |
4 | | David R. Karger,
Daphne Koller,
Steven J. Phillips:
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths.
SIAM J. Comput. 22(6): 1199-1217 (1993) |
1992 |
3 | EE | Douglas R. Cutting,
Jan O. Pedersen,
David R. Karger,
John W. Tukey:
Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections.
SIGIR 1992: 318-329 |
2 | EE | David R. Karger,
Noam Nisan,
Michal Parnas:
Fast Connected Components Algorithms for the EREW PRAM.
SPAA 1992: 373-381 |
1991 |
1 | | David R. Karger,
Daphne Koller,
Steven J. Phillips:
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
FOCS 1991: 560-568 |