2009 (4)

Bridging High-Throughput Genetic and Transcriptional Data Reveals Cellular Responses to Alpha-Synuclein Toxicity

Yeger-Lotem, Esther, Riva, Laura, Su, L.J., Gitler, A.D., Cashikar, A.G., King, O.D., Auluck, P.K., Geddie, M.L., Valastyan, J.S., Karger, David R., Lindquist, Susan, and Fraenkel, Ernest

Nature Genetics 41 (3) , March 2009 (pp. 316-23)

download
Global Models of Document Structure Using Latent Permutations

Chen, Harr, Branavan, S.R.K., Barzilay, Regina, and Karger, David R.

North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL HLT) conference , May 2009
A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges

Bernstein, Aaron and Karger, David

Proceedings of the {$40^{th}$} {ACM} Symposium on Theory of Computing , May 2009 (pp. 101--110)

pdf
Examining Personal Information-Keeping in a Lightweight Note-Taking Tool

Van Kleek, Max,, Bernstein, Michael, Vargas, Greg, Panovich, Katrina, Karger, David, and schraefel, mc

Proceedings of the ACM CHI Conference on Human Factors in Computing Systems , April 2009 Best note nominee

2008 (5)

Information Scraps: How and Why Information Eludes our Personal Information Management Tools

Bernstein, Michael, Van Kleek, Max, Karger, David R., and {s}chraefel, {m}c

ACM Transactions on Information Systems 26 (4) , 2008 (pp. 1--46) special issue on PIM

doi
Improved Approximations for Multiprocessor Scheduling Under Uncertainty

Crutchfield, Christopher Y., Dzunic, Zoran, Fineman, Jeremy T., Karger, David R., and Scott, Jacob H.

Proceedings of the Twentieth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , June 2008
Inky: A Sloppy Command Line for the Web with Rich Visual Feedback

Miller, Rob, Chou, Victoria, Bernstein, Michael, Little, Greg, Kleek, Max Van, Karger, David, and schraefel, mc

21st Symposium on User Interface Software Technology (UIST) , October 2008 (pp. 131--140)
AtomsMasher: Personal Reactive Automation for the Web

Van Kleek, Max, Andre, Paul, Perttunen, Mikko, Karger, David, Miller, Rob, and schraefel, mc

21st Symposium on User Interface Software Technology (UIST) , October 2008 poster paper
Improved Distance Sensitivity Oracles via Random Sampling

Bernstein, Aaron and Karger, David

Proceedings of the {$19^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2008 (pp. 34-43)

pdf

2007 (12)

It's All the Same to Me: Data Unification in Personal Information Management

Karger, David R.

in William Jones and Jaime Teevan, editors, Personal Information Management , 2007 (pp. 127-152)

pdf

Click for abstract:
Information fragmentation is a pervasive problem in personal information management. Even a seemingly simple decision, such as whether to say "yes" to a dinner invitation, often depends upon information from several sources---a calendar, a paper flyer, web sites, a previous email conversation, etc. This information is fragmented by the very tools that have been designed to help us manage it. Applications often store their data in their own particular locations and representations, inaccessible to other applications. Consider the information Alex maintains about Brooke. He must keep Brooke's address in his address book, his picture in a photo album, his home page in his web bookmarks, a birthday invitation he is editing with her in his file system, and an appointment with her in his calendar. This fragmentation causes numerous problems. There is no one "directory" Alex can use to find all the information about Brooke; nor any way to "link" pieces of information about Brooke to each other. Instead, Alex must launch multiple applications and perform numerous repetitive searches for relevant information, to say nothing of deciding which applications to look in. He may change data in one place (a new married name in the address book) and fail to change it elsewhere, leading to inconsistency that makes it even harder to find information (which name does Alex use to search the photo album?). While the computer has fragmented information, it can also be used to put the pieces together again. This chapter surveys some of the ways in which our personal information might be better unified.
Haystack: Per-User Information Environments

Karger, David R.

in Victor Kaptelinin and Mary Czerwinski, editors, Beyond the Desktop Metaphor: Designing Integrated Digital Work Environments , 2007 (pp. 49-100)

pdf

Click for abstract:
Haystack is a system that aims to maximize every individual user's control over the way he or she records, views, organizes, and searches for information. In this paper we discuss the elements of the system: a flexible semantic-net data model that can stretch to accomodate whatever information, relationships, properties, and categories a user considers important, and a user interface framework that can effecively display the personalized information space in ways that make sense to and can be customized by the end user.
Management of personal information scraps

Bernstein, Michael S., Kleek, Max Van, schraefel, m. c., and Karger, David R.

CHI Extended Abstracts , May 2007 (pp. 2285-2290) Poster.

pdf

Click for abstract:
We introduce research on information scraps. short, self-contained personal notes that fall outside of traditional filing schemes. We report on a preliminary study of information scraps. nature and outline plans for the next phase of our user study. Based on ongoing study results, we describe our designs and prototypes for information scrap capture and access tools.
{U-REST}: an unsupervised record extraction system

Shen, Yuan Kui and Karger, David R.

16th International World Wide Web Conference (WWW2007) , May 2007 (pp. 1347-1348) Poster.

pdf

Click for abstract:
We demonstrate a system that extracts record sets from record-list web pages with no direct human supervision. Our system, U-REST, reframes the problem of unsupervised record extraction as a two-phase machine learning problem with a clustering phase, where structurally similar regions are discovered, and a record cluster detection phase, where discovered grouping of regions are ranked by their likelihood of being records. This framework simplifies the record extraction task, and allows for independent analysis of the algorithms and the underlying features. In our work, we survey a large set of features under this simplified framework. We conclude with an preliminary comparison of U-REST against similar systems and show improvements in the extraction accuracy.
{GUI} --- Phooey!: The Case for Text Input

Kleek, Max Van, Bernstein, Michael, Karger, David R., and schraefel, mc

UIST '07: Proceedings of the 20th annual ACM symposium on User interface software and technology , October 2007 (pp. 193--202)

pdf doi
Subjective Cost Policy Routing

Feigenbaum, Joan, Karger, David R., Mirrokni, Vahab S., and Sami, Rahul

Theoretical Computer Science 378 (2) , June 2007 (pp. 174--183)

pdf ps doi

Click for abstract:
We study a model of interdomain routing in which autonomous systems' (ASes') routing policies are based on {\em subjective} cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance ASes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each AS to have a route that nearly minimizes its subjective cost; these routing trees can be computed easily with a distributed algorithm. Furthermore, we prove that this bound is almost tight.
Exhibit: Lightweight Structured Data Publishing

Huynh, David, Miller, Robert, and Karger, David R.

WWW 2007 , May 2007 (pp. 737--746)

pdf

Click for abstract:
It is no surprise that Semantic Web researchers and enthusiasts are excited to publish and accumulate semi-structured data on the Web. Beyond our community, however, we see many authors with structured data who want to publish it in rich browsing interfaces. These small-time authors are similar to early enthusiasts of the Web, simply excited by the opportunity to use a new medium to share information that they care about. For these users, we propose Exhibit, a lightweight structured data publishing framework that duplicates many of the desirable properties that contributed to the original growth of the Web. We argue that appealing to this segment of the Web population?addressing their publishing needs at very low cost?lets us leverage their labor to put structure on content that otherwise would be published in hand-authored HTML, and thus very hard to harvest automatically.
Potluck: Data Mash-Up Tool for Casual Users

Huynh, David, Miller, Robert, and Karger, David R.

$6^{th}$ International Semantic Web Conference (ISWC) , November 2007 to appear

pdf

Click for abstract:
As more and more reusable structured data appears on the Web, casual users will want to take into their own hands the task of mashing up data rather than wait for mash-up sites to be built that address exactly their individually unique needs. In this paper, we present Potluck, a Web user interface that lets casual users?those without programming skills and data modeling expertise?mash up data themselves.
Potluck is novel in its use of drag and drop for merging fields, its integration and extension of the faceted browsing paradigm for focusing on subsets of data to align, and its application of simultaneous editing for cleaning up data syntactically. Potluck also lets the user construct rich visualizations of data in-place as the user aligns and cleans up the data. This iterative process of integrating the data while constructing useful visualizations is desirable when the user is unfamiliar with the data at the beginning?a common case?and wishes to get immediate value out of the data without having to spend the overhead of completely and perfectly integrating the data first.
A user study on Potluck indicated that it was usable and learnable, and elicited excitement from programmers who, even with their programming skills, previously had great difficulties performing data integration.
Approximation Algorithms for Orienteering and Discounted-Reward TSP

Blum, Avrim, Chawla, Shuchi, Karger, David R., Lane, Terran, Meyerson, Adam, and Minkoff, Maria

SIAM Journal on Computing 37 (2) , 2007 (pp. 653-670) A preliminary version appeared in Proceedings of the {$36^{th}$} Annual Symposium on the Foundations of Computer Science

doi
Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems

Karger, David R. and Onak, Krzysztof

Proceedings of the {$18^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2007 (pp. 1207-1216)
Randomized Decoding for Selection-and-Ordering Problems

Deshpande, Pawan, Barzilay, Regina, and Karger, David

Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference , April 2007 (pp. 444--451)

pdf

Click for abstract:
The task of selecting and ordering information appears in multiple contexts in text generation and summarization. For instance, methods for title generation construct a headline by selecting and ordering words from the input text. In this paper, we investigate decoding methods that simultaneously optimize selection and ordering preferences. We formalize decoding as a task of finding an acyclic path in a directed weighted graph. Since the problem is NP-hard, finding an exact solution is challenging. We describe a novel decoding method based on a randomized color-coding algorithm. We prove bounds on the number of color-coding iterations necessary to guarantee any desired likelihood of finding the correct solution. Our experiments show that the randomized decoder is an appealing alternative to a range of decoding algorithms for selection-and-ordering problems, including beam search and Integer Linear Programming.
Piggy Bank: Experience the Semantic Web Inside your Web Browser

Huynh, David, Mazzochi, Stefano, and Karger, David

Journal of Web Semantics 5 (1) , 2007 (pp. 16-27)

pdf

Click for abstract:
The Semantic Web Initiative envisions a Web wherein information is offered free of presentation, allowing more effective exchange and mixing across web sites and across web pages. But without substantial Semantic Web content, few tools will be written to consume it; without many such tools, there is little appeal to publish Semantic Web content.
To break this chicken-and-egg problem, thus enabling more flexible information access, we have created a web browser extension called Piggy Bank that lets users make use of Semantic Web content within Web content as users browse the Web. Wherever Semantic Web content is not available, Piggy Bank can invoke screenscrapers to re-structure information within web pages into Semantic Web format. Through the use of Semantic Web technologies, Piggy Bank provides direct, immediate benefits to users in their use of the existing Web. Thus, the existence of even just a few Semantic Web-enabled sites or a few scrapers already benefits users. Piggy Bank thereby offers an easy, incremental upgrade path to users without requiring a wholesale adoption of the Semantic Web's vision.
To further improve this Semantic Web experience, we have created Semantic Bank, a web server application that lets Piggy Bank users share the Semantic Web information they have collected, enabling collaborative efforts to build sophisticated Semantic Web information repositories through simple, everyday's use of Piggy Bank.

2006 (12)

The Pathetic Fallacy of RDF

Karger, David R. and schraefel, m. c.

SWUI 2006 - 3rd International Semantic Web User Interaction Workshop , November 2006 collocated with ISWC 2006

download
Enabling Web Browsers to Augment Web Sites' Filtering and Sorting Functionalities

Huynh, David F., Miller, Robert C., and Karger, David R.

Proceedings of the ACM Symposium on User Interface Software and Technology (UIST) , May 2006 (pp. 125--134)

pdf

Click for abstract:
Existing augmentations of web pages are mostly small cosmetic changes (e.g., removing ads) and minor addition of third-party content (e.g., product prices from competing sites). None leverages the structured data presented in web pages. This paper describes Sifter, a web browser extension that can augment a web site with advanced filtering and sorting functionality. These added features work inside the site's own pages, preserving the site's presentational style, as if the site itself has implemented the features. Sifter contains an algorithm that scrapes structured data out of web pages while usually requiring no user intervention. We tested Sifter on real web sites and real users and found that people could use Sifter to perform sophisticated queries and high-level analyses on sizable data collections on the Web. We propose that web sites can be similarly augmented with other sophisticated data-centric functionality, giving users new benefits over the existing Web.
Relo: Helping Users Manage Context during Interactive Exploratory Visualization of Large Codebases

Sinha, Vineet, Karger, David R., and Miller, Robert C.

VL/HCC: Visual Languages and Human Centered Computing , September 2006 (pp. 187-194)

pdf

Click for abstract:
As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this paper, we present a tool, Relo, that supports developers? understanding by allowing interactive exploration of code. As the developer explores relationships found in the code, Relo builds and automatically manages the context in a visualization, thereby helping build the developer?s mental representation of the code. Developers can group viewed artifacts or use the viewed items to ask Relo for further exploration suggestions, with Relo providing features to limit the growth of the diagram. To ensure developers don?t get overwhelmed, Relo has been built with a user-centered approach, and preliminary evaluations with developers exploring new code have shown them to find the tool intuitive and helpful.
Simple efficient load balancing algorithms for peer-to-peer systems

Karger, David R. and Ruhl, Matthias

Theory of Computing Systems 39 (6) , November 2006 (pp. 787--804) Preliminary versions in IPTPS 2004 and SPAA 2004

pdf

Click for abstract:
Load balancing is a critical issue for the efficient operation of peer-to-peer (P2P) networks. We give two new load-balancing protocols whose provable performance guarantees are within a constant factor of optimal. Our protocols refine the consistent hashing data structure that underlies the Chord (and Koorde) P2P network. Both preserve Chord's logarithmic query time and near-optimal data migration cost. Consistent hashing is an instance of the distributed hash table (DHT) paradigm for assigning items to nodes in a P2P system: items and nodes are mapped to a common address space, and nodes have to store all items residing closeby in the address space. Our first protocol balances the distribution of the key address space to nodes, which yields a load-balanced system when the DHT maps items "randomly" into the address space. To our knowledge, this yields the first P2P scheme simultaneously achieving O(log n) degree, O(log n) look-up cost, and constant-factor load balance (previous schemes settled for any two of the three). Our second protocol aims to balance directly the distribution of items among the nodes. This is useful when the distribution of items in the address space cannot be randomized. We give a simple protocol that balances load by moving nodes to arbitrary locations "where they are needed." As an application, we use the last protocol to give an optimal implementation of a distributed data structure for range searches on ordered data.
The Complexity of Matrix Completion

Harvey, Nicholas J. A., Karger, David R., and Yekhanin, Sergey

Proceedings of the {$17^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2006 (pp. 1103--1111)

pdf doi
Data Unification in Personal Information Management

Karger, David R. and Jones, William

Communications of the ACM 49 (1) , January 2006 (pp. 77-82)

doi

Click for abstract:
Users need ways to unify, simplify, and consolidate information too often fragmented by location, device, and software application.
A Random Linear Network Coding Approach to Multicast

Ho, Tracey, M\'{e}dard, Muriel, Koetter, Ralf, Karger, David R., Effros, Michelle, Shi, J., and Leong, B.

IEEE Transactions on Information Theory 52 (10) , 2006 (pp. 4413-4430)

pdf

Click for abstract:
We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian?Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks.
Minimum-cost multicast over coded packet networks

Lun, Desmond S., Ratnakar, Niranjan, M\'{e}dard, Muriel, Koetter, Ralf, Karger, David R., Ho, Tracey, Ahmed, Ebad, and Zhao, Fang

IEEE Transactions on Information Theory 52 (6) , 2006 (pp. 2608-2623)

Click for abstract:
We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e. packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.
Distributed Quota Enforcement for Spam Control

Walfish, Michael, Zamfirescu, J. D., Balakrishnan, Hari, Karger, David R., and Shenker, Scott

NSDI: Networking Systems Design and Implementation , May 2006

pdf

Click for abstract:
Spam, by overwhelming inboxes, has made email a less reliable medium than it was just a few years ago. Spam filters are undeniably useful but unfortunately can flag non-spam as spam. To restore email's reliability, a recent spam control approach grants quotas of stamps to senders and has the receiver communicate with a wellknown quota enforcer to verify that the stamp on the email is fresh and to cancel the stamp to prevent reuse. The literature has several proposals based on this general idea but no complete system design and implementation that: scales to today's email load (which requires the enforcer to be distributed over many hosts and to tolerate faults in them), imposes minimal trust assumptions, resists attack, and upholds today's email privacy. This paper describes the design, implementation, analysis, and experimental evaluation of DQE, a spam control system that meets these challenges. DQE's enforcer occupies a point in the design spectrum notable for simplicity: mutually untrusting nodes implement a storage abstraction but avoid neighbor maintenance, replica maintenance, and heavyweight cryptography.
Less is more: probabilistic models for retrieving fewer relevant documents

Chen, Harr and Karger, David R.

$29^{th}$ Internationl ACM SIGIR Conference , July 2006 (pp. 429-436)

pdf

Click for abstract:
Traditionally, information retrieval systems aim to maximize the number of relevant documents returned to a user within some window of the top. For that goal, the probability ranking principle, which ranks documents in decreasing order of probability of relevance, is provably optimal. However, there are many scenarios in which that ranking does not optimize for the user?s information need. One example is when the user would be satisfied with some limited number of relevant documents, rather than needing all relevant documents. We show that in such a scenario, an attempt to return many relevant documents can actually reduce the chances of finding any relevant documents. We consider a number of information retrieval metrics from the literature, including the rank of the first relevant result, the %no metric that penalizes a system only for retrieving no relevant results near the top, and the diversity of retrieved results when queries have multiple interpretations. We observe that given a probabilistic model of relevance, it is appropriate to rank so as to directly optimize these metrics in expectation. While doing so may be computationally intractable, we show that a simple greedy optimization algorithm that approximately optimizes the given objectives produces rankings for TREC queries that outperform the standard approach based on the probability ranking principle.
Optimal Route Planning under Uncertainty

Nikolova, Evdokia, Brand, Matthew, and Karger, David

Proceedings of 2006 International Conference on Automated Planning and Scheduling (ICAPS 2006) , June 2006

pdf

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

Pietriga, Emmanuel, Bizer, Chris, Karger, David, and Lee, Ryan

$5^{th}$ International Semantic Web Conference (ISWC) , November 2006 (pp. 158--171)

pdf

Click for abstract:
Semantic Web browsers and other tools aimed at displaying RDF data to end users are all concerned with the same problem: presenting content primarily intended for machine consumption in a human-readable way. Their solutions differ but in the end address the same two high-level issues, no matter the underlying representation paradigm: specifying (i) what information contained in RDF models should be presented (content selection) and (ii) how this information should be presented (content formatting and styling). However, each tool currently relies on its own ad hoc mechanisms and vocabulary for specifying RDF presentation knowledge, making it difficult to share and reuse such knowledge across applications. Recognizing the general need for presenting RDF content to users and wanting to promote the exchange of presentation knowledge, we designed Fresnel as a browser-independent vocabulary of core RDF display concepts. In this paper we describe Fresnel's main concepts and present several RDF browsers and visualization tools that have adopted the vocabulary so far.

2005 (15)

OverCite: A Cooperative Digital Research Library

Stribling, Jeremy, Councill, Isaac G., Li, Jinyang, Kaashoek, M. Frans, Karger, David R., Morris, Robert, and Shenker, Scott

4th International Workshop on Peer to Peer Systems , February 2005 (pp. 69--79)

pdf doi

Click for abstract:
CiteSeer is a well-known online resource for the computer science research community, allowing users to search and browse a large archive of research papers. Unfortunately, its current centralized incarnation is costly to run. Although members of the community would presumably be willing to donate hardware and bandwidth at their own sites to assist CiteSeer, the current architecture does not facilitate such distribution of resources. OverCite is a design for a new architecture for a distributed and cooperative research library based on a distributed hash table (DHT). The new architecture harnesses donated resources at many sites to provide document search and retrieval service to researchers worldwide. A preliminary evaluation of an initial OverCite prototype shows that it can service more queries per second than a centralized system, and that it increases total storage capacity by a factor of n/4 in a system of n nodes. OverCite can exploit these additional resources by supporting new features such as document alerts, and by scaling to larger data sets.
Arpeggio: Metadata Searching and Content Sharing with Chord

Clements, Austin T., Ports, Dan R. K., and Karger, David R.

4th International Workshop on Peer to Peer Systems , February 2005 (pp. 58--68)

pdf doi

Click for abstract:
Arpeggio is a peer-to-peer file-sharing network based on the Chord lookup primitive. Queries for data whose metadata matches a certain criterion are performed efficiently by using a distributed keyword-set index, augmented with index-side filtering. We introduce index gateways, a technique for minimizing index maintenance overhead. Because file data is large, Arpeggio employs subrings to track live source peers without the cost of inserting the data itself into the network. Finally, we introduce postfetching, a technique that uses information in the index to improve the availability of rare files. The result is a system that provides efficient query operations with the scalability and reliability advantages of full decentralization, and a content distribution system tuned to the requirements and capabilities of a peer-to-peer network.
Subjective Cost Policy Routing

Feigenbaum, Joan, Karger, David R., Mirrokni, Vahab S., and Sami, Rahul

Internet and Network Economics: First International Workshop, WINE 2005 , December 2005 (pp. 174--183)

doi

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

Harvey, Nicholas J. A., Karger, David R., and Murota, Kazuo

Proceedings of the {$16^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2005

pdf ps
Magnet: supporting navigation in semistructured data environments

Sinha, Vineet and Karger, David R.

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data , 2005 (pp. 97--106)

pdf doi

Click for abstract:
With the growing importance of systems containing arbitrary semistructured relationships, the need for supporting users searching in such repositories has grown. Currently support for users? search needs either has required domain-specific user interfaces or has required users to be schema experts. We have developed a generalpurpose tool that offers users helpful navigation and refinement options for seeking information in these semistructured repositories. We show how a tool can be built without requiring domain-specific assumptions about the information being explored. In addition to describing a general approach to the problem, we provide a set of natural, general-purpose refinement tactics, many generalized from past work on textual information retrieval.
Haystack: A General Purpose Information Management Tool for End Users of Semistructured Data

Karger, David R., Bakshi, Karun, Huynh, David, Quan, Dennis, and Sinha, Vineet

Conference on Innovative Database Research (CIDR) , 2005 (pp. 13--26)

pdf

Click for abstract:
We posit that a semistructured data model offers the right balance of rich structure and flexible (or lack of) schema allowing naive end users to record information in whatever form makes it easy for them to manage. We describe our Haystack system, which exposes the richness and flexibility of the data model while offering the user natural, traditional interfaces that shield them from the specifics of schemas, tuples, and database queries. We outline research challenges that remain to be addressed.
Toward Using the Network as a Switch

Karger, David and Medard, Muriel

IEEE Journal on Selected Areas in Communications: Optical Communications and Networking Series 23 (8) , August 2005 (pp. 1533--1541)

Click for abstract:
A common problem in optical networking is that the large quantity of raw bandwidth available in such networks is often difficult to access. We show that time-division multiplexing (TDM) can be used to operate bus and ring architectures in a manner akin to a switch. Doing so substantially reduces the amount of hardware [particularly, add?drop multiplexers (ADMs)] needed to utilize fully the available bandwidth in a range of optical networks. We show that a significant fraction (and in some cases all) of the bandwidth available to the system can be utilized even if each node in the system has only a single ADM. Our approach is probabilistic in nature, using generalizations of the Birkhoff-von Neumann statistical multiplexing approaches that have been successful in switching theory. Our techniques rely on decompositions of fractional matchings (for architectures without erasures) and fractional interval graph colorings (for architectures with erasures) into integral matchings and colorings.
Incremental exploratory visualization of relationships in large codebases for program comprehension

Sinha, Vineet, Miller, Robert C., and Karger, David

OOPSLA'05 Eclipse Technology eXchange (ETX) Workshop , October 2005 (pp. 116--117)

pdf doi

Click for abstract:
As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this poster, we present a tool, Relo that supports users' understanding by allowing interactive exploration of code. As the developer explores relationships found in the code, Relo builds and automatically manages a visualization mirroring the developer's mental model, allowing them to group viewed artifacts or use the viewed items to ask the system for further exploration suggestions.
{DoS:} Fighting Fire with Fire

Walfish, Michael, Balakrishnan, Hari, Karger, David, and Shenker, Scott

4th ACM Workshop on Hot Topics in Networks (HotNets) , November 2005

pdf

Click for abstract:
We consider DoS attacks on servers in which attackers' requests are indistinguishable from legitimate requests. Most current defenses against this class of attack rely on legitimate users in aggregate having more of some resource (CPU cycles, memory cycles, human attention, etc.) than attackers. A server so defended asks prospective clients to prove their legitimacy by spending some of this resource. We adopt this general approach but use bandwidth as the constrained resource. Specifically, we argue that when a server is attacked, it should: (1) prevent overloading by limiting the incoming rate of requests (and dropping all others) and (2) encourage its legitimate clients to fight back with aggressive retransmission. This approach forces all clients to spend bandwidth to receive service, and the legitimate clients, with their greater aggregate bandwidth, will receive the bulk of the service.
Local Decoding of Walsh Codes to Reduce CDMA Despreading Computation

Chan, A., Feldman, Jon, Madyastha, Raghu, Indyk, Piotr, and Karger, David

Sotware Defined Radio Technical Conference , November 2005

pdf

Click for abstract:
In traditional hardware implementations of the CDMA standard IS-95 [1], signals received at the base station are despread at a rate of 1.2288 Megachips/sec prior to Walsh decoding. However, in a software implementation where low computational complexity is critical, despreading at such a high rate imposes a strain on computational resources. In this paper, we take advantage of the flexibility afforded by software implementations and develop three classes of Walsh decoding algorithms that do not require full despreading of incoming signals at the base station. Two proposed classes of algorithms exploit the fact that Walsh codes are locally decodable codes, which have the surprising property that any bit of the message can be recovered (with some probability) by examining only a small number of symbols of the codeword. We also describe a third class of algorithms based on code puncturing. All these algorithms enable trading off computation for performance or, from another perspective, they enable the system to dynamically adapt the computational requirements of the despreader and subsequent Walsh decoder to changing channel conditions such that a target bit-error rate (BER) is maintained. These algorithms are applicable to other CDMA-based systems that use Walsh codes for orthogonal modulation, and the third class is also applicable to CDMA-based systems such as UMTS (3G WCDMA) that use codes for channelization
First-price path auctions

Immorlica, Nicole, Karger, David, Nikolova, Evdokia, and Sami, Rahul

EC '05: Proceedings of the 6th ACM conference on Electronic commerce , June 2005 (pp. 203--212)

ps doi

Click for abstract:
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all {\it strong $\epsilon$-Nash equilibria} of a first-price auction for this problem, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves (VCG) mechanism. We then present a randomized version of the first-price auction, for which the equilibrium condition can be relaxed to $\epsilon$-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known to the edges. For this model, we show that a simple {\em ex ante} first-price auction may not have any $\epsilon$-Nash equilibria. We then present a modified auction mechanism with $2$-parameter bids, and show that it has an $\epsilon$-Nash equilibrium.
Thresher: Automating the Unwrapping of Semantic Content from the World Wide Web

Hogue, Andrew and Karger, David

Proceedings of the $14^{th}$ International World Wide Web Conference (WWW) , May 2005 (pp. 86--95)

pdf

Click for abstract:
We describe Thresher, a system that lets non-technical users teach their browsers how to extract semantic web content from HTML documents on the World Wide Web. Users specify examples of semantic content by highlighting them in a web browser and describing their meaning. We then use the tree edit distance between the DOM subtrees of these examples to create a general pattern, or wrapper, for the content, and allow the user to bind RDF classes and predicates to the nodes of these wrappers. By overlaying matches to these patterns on standard documents inside the Haystack semantic web browser, we enable a rich semantic interaction with existing web pages, \unwrapping" semantic data buried in the pages' HTML. By allowing end-users to create, modify, and utilize their own patterns, we hope to speed adoption and use of the Semantic Web and its applications.
End-User Application Development for the Semantic Web

Bakshi, Karun and Karger, David

Semantic Desktop 2005 Workshop, International Semantic Web Conference (ISWC) , October 2005

pdf

Click for abstract:
Although a lot of information has become readily accessible and necessary for daily work, the current infrastructure for managing information is ill-suited for information-oriented activities: information and functionality are scattered across applications and websites, making it difficult to aggregate and reuse just the right set of content and operations required for unique user tasks. We discuss a collection of tools built into the Haystack platform that address many of the shortcomings of current applications, and allow composing reusable fragments of information and associated operations and views from the Semantic Web into a task workspace tailored to the user and the task. Users can change the workspace to immediately meet changing requirements to easily include, remove or reuse information in multiple tasks simultaneously. The time that a user invests for the initial setup and occasional updates to the workspace is amortized over the numerous times he or she returns to the task, and all relevant information resources are co-located and ready to use.
Using Linear Programming to Decode Linear Codes

Feldman, Jon, Karger, David, and Wainwright, Martin

IEEE Transactions on Information Theory 51 (3) , March 2005 (pp. 954-972)

download

Click for abstract:
Abstract: A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting \emph{LP decoder} generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including \emph{stopping sets,} \emph{irreducible closed walks,} \emph{trellis cycles,} \emph{deviation sets,} and \emph{graph covers.} The fractional distance frac of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to frac 2 1 errors and that there are codes with frac = ( 1 ). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided. Index Terms: Belief propagation (BP), iterative decoding, low density parity-check (LDPC) codes, linear codes, linear programming (LP), LP decoding, minimum distance, pseudocodewords.
Piggy Bank: Experience the Semantic Web Inside your Web Browser

Huynh, David, Mazzochi, Stefano, and Karger, David

International Semantic Web Conference (ISWC) , 2005

pdf

Click for abstract:
The Semantic Web Initiative envisions a Web wherein information is offered free of presentation, allowing more effective exchange and mixing across web sites and across web pages. But without substantial Semantic Web content, few tools will be written to consume it; without many such tools, there is little appeal to publish Semantic Web content.
To break this chicken-and-egg problem, thus enabling more flexible information access, we have created a web browser extension called Piggy Bank that lets users make use of Semantic Web content within Web content as users browse the Web. Wherever Semantic Web content is not available, Piggy Bank can invoke screenscrapers to re-structure information within web pages into Semantic Web format. Through the use of Semantic Web technologies, Piggy Bank provides direct, immediate benefits to users in their use of the existing Web. Thus, the existence of even just a few Semantic Web-enabled sites or a few scrapers already benefits users. Piggy Bank thereby offers an easy, incremental upgrade path to users without requiring a wholesale adoption of the Semantic Web's vision.
To further improve this Semantic Web experience, we have created Semantic Bank, a web server application that lets Piggy Bank users share the Semantic Web information they have collected, enabling collaborative efforts to build sophisticated Semantic Web information repositories through simple, everyday's use of Piggy Bank.

2004 (13)

How to Make a Semantic Web Browser

Quan, Dennis and Karger, David R.

Proceedings of the $13^{th}$ International World Wide Web Conference , May 2004 (pp. 255--265)

pdf

Click for abstract:
Two important architectural choices underlie the success of the Web: numerous, independently operated servers speak a common protocol, and a single type of client-the Web browser-provides point-and-click access to the content and services on these decentralized servers. However, because HTML marries content and presentation into a single representation, end users are often stuck with inappropriate choices made by the Web site designer of how to work with and view the content. RDF metadata on the Semantic Web does not have this limitation: users can gain direct access to the underlying information and control how it is presented for themselves. This principle forms the basis for our Semantic Web browser-an end user application that automatically locates metadata and assembles point-and-click interfaces from a combination of relevant information, ontological specifications, and presentation knowledge, all described in RDF and retrieved dynamically from the Semantic Web. With such a tool, naive users can begin to discover, explore, and utilize Semantic Web data and services. Because data and services are accessed directly through a standalone client and not through a central point of access (e.g., a portal), new content and services can be consumed as soon as they become available. In this way we take advantage of an important sociological force that encourages the production of new Semantic Web content by remaining faithful to the decentralized nature of the Web.
Using URLs and Table Layout for Web Classification Tasks

Shih, Kai and Karger, David R.

Proceedings of the $13^{th}$ International World Wide Web Conference , May 2004

pdf

Click for abstract:
We propose new features and algorithms for automating Web-page classification tasks such as content recommendation and ad blocking. We show that the automated classification of Web pages can be much improved if, instead of looking at their textual content, we consider each links's URL and the visual placement of those links on a referring page. These features are unusual: rather than being scalar measurements like word counts they are \emph{tree structured}---describing the position of the item in a tree. We develop a model and algorithm for machine learning using such tree-structured features. We apply our methods in automated tools for recognizing and blocking Web advertisements and for recommending ``interesting'' news stories to a reader. Experiments show that our algorithms are both faster and more accurate than those based on the text content of Web documents.
Load Balancing in P2P Systems

Karger, David R. and Ruhl, Matthias

IPTPS: 3rd International Workshop on Peer to Peer Systems , February 2004

pdf

Click for abstract:
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant factor of optimal. First, we give an improved version of consistent hashing, a scheme used for item to node assignments in the Chord system. In its original form, it required every network node to operate $O(\log n)$ virtual nodes to achieve a balanced load, causing a corresponding increase in space and bandwidth usage. Our protocol eliminates the necessity of virtual nodes while maintaining a balanced load. Improving on related protocols, our scheme allows for the deletion of nodes and admits a simpler analysis, since the assignments do not depend on the history of the network. We then analyze several simple protocols for load sharing by movements of data from higher loaded to lower loaded nodes. These protocols can be extended to preserve the ordering of data items. As an application, we use the last protocol to give an efficient implementation of a distributed data structure for range searches on ordered data.
Simple efficient load balancing algorithms for peer-to-peer systems

Karger, David R. and Ruhl, Matthias

SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures , June 2004 (pp. 36--43) Preliminary version in IPTPS 2004

pdf ps doi

Click for abstract:
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give two new load-balancing protocols whose provable performance guarantees are within a constant factor of optimal. Our protocols refine the consistent hashing data structure that underlies the Chord (and Koorde) P2P network. Both preserve Chord's logarithmic query time and near-optimal data migration cost.Consistent hashing is an instance of the distributed hash table (DHT) paradigm for assigning items to nodes in a peer-to-peer system: items and nodes are mapped to a common address space, and nodes have to store all items residing closeby in the address space.Our first protocol balances the distribution of the key address space to nodes, which yields a load-balanced system when the DHT maps items "randomly" into the address space. To our knowledge, this yields the first P2P scheme simultaneously achieving O(log n) degree, O(log n) look-up cost, and constant-factor load balance (previous schemes settled for any two of the three).Our second protocol aims to directly balance the distribution of items among the nodes. This is useful when the distribution of items in the address space cannot be randomized. We give a simple protocol that balances load by moving nodes to arbitrary locations "where they are needed." As an application, we use the last protocol to give an optimal implementation of a distributed data structure for range searches on ordered data.
Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer to Peer Systems

Karger, David R. and Ruhl, Matthias

Proceedings of the {$15^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2004

pdf ps

Click for abstract:
In most of the P2P systems developed so far, all nodes play essentially the same role. In some applications, however, different machine capabilities or owner preferences may mean that only a subset of nodes in the system should participate in offering a particular service. Arranging for each service to be supported by a different peer to peer network is, we argue here, a wasteful solution. Instead, we propose a version of the Chord peer-to-peer protocol that allows any subset of nodes in the network to jointly offer a service without forming their own Chord ring. Our variant supports the same efficient join/leave/insert/delete operations that the subgroup would get if they did form their own separate peer to peer network, but requires significantly less resources than the separate network would. For each subgroup of k machines, our protocol uses O(k) additional storage in the primal Chord ring. The insertion or deletion of a node in the subgroup and the lookup of the next node of a subgroup all require O(log n) hops.
Optimal Rounding Algorithms for a Geometric Embedding of the Multiway Cut Problem

Karger, David R., Klein, Philip N., Stein, Clifford, Thorup, Mikkel, and Young, Neal

Mathematics of Operations Research 29 (3) , 2004 (pp. 436--461)

pdf

Click for abstract:
Given an undirected graph with edge costs and a subset of k = 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to .nd a minimum-cost multiway cut. This problem is Max-SNP hard. Recently, Calinescu et al. (Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for Multiway Cut. J. Comput. System Sci. 60(3) 564-574) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3/2-1/k)-approximation algorithm. In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k =3, we show the integrality gap is 12/11, giving tight upper and lower bounds. That is, we exhibit a family of graphs with integrality gaps arbitrarily close to 12/11 and give an algorithm that .nds a cut of value 12/11 times the relaxation value. Our lower bound shows that this is the best possible performance guarantee for any algorithm based purely on the value of the relaxation. Our upper bound meets the lower bound and improves the factor of 7/6 shown by Calinescu et al. For all k, we show that there exists a rounding scheme with performance ratio equal to the integrality gap, and we give explicit constructions of polynomial-time rounding schemes that lead to improved upper bounds. For k = 4 and 5, our best upper bounds are based on computer-constructed rounding schemes (with computer proofs of correctness). For general k we give an algorithm with performance ratio 1.3438-ek. Our results were discovered with the help of computational experiments that we also describe here.
Decoding Turbo-Like Codes via Linear Programming

Feldman, Jon and Karger, David R.

Journal of Computer and System Sciences 68 (4) , 2004 (pp. 733--752) Special Issue of Best Papers from FOCS 2002.

pdf doi

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

Ho, Tracey, Leong, B., Koetter, Ralf, M\'{e}dard, Muriel, Effros, Michelle, and Karger, David R.

International Symposium on Information Theory (ISIT) , 2004

pdf

Click for abstract:
Distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without the use of cryptographic functions is presented in this paper.
Haystack: A User Interface for Creating, Browsing and Organizing Arbitrary Semistructured Information

Quan, Dennis and Karger, David R.

Proceedings of the ACM CHI Conference on Human Factors in Computing Systems , 2004 Demo

doi

Click for abstract:
Much past HCI research has examined the usability concerns of information management software for specific domains such as object-oriented software design, e-mail, and the Web. We believe that many of the results uncovered by these studies are applicable across multiple domains but that more broadly-scoped experiments require a system that can integrate multiple data sources. Haystack is a general-purpose information management environment designed to attack this very problem. Haystack's user interface, which incorporates capabilities from previous research such as context-specific visualization paradigms and attribute-based categorization, is built upon a highly expressive semistructured data model and data integration capabilities. In our demonstration we show how combination of a direct-manipulation-based UI paradigm and an expressive, federated data model can begin to address many of the information management problems plaguing general desktop computing today and can serve as a basis for further, yet unexplored, crossover information interaction experiments.
{Spam-I-am}: A Proposal for Spam Control Using Distributed Quota Management

Balakrishnan, Hari and Karger, David R.

Proceedings of the Third Annual ACM SIGCOMM Workshop on Hot Topics in Networking ({HotNets-III}) , November 2004

pdf

Click for abstract:
Email spam has reached alarming proportions because it costs virtually nothing to send email; even a small number of people responding to a spam message is adequate incentive for a spammer to send as many messages as possible. Since spammers need to send messages at high rates to as many recipients as they can, quotas on email senders could throttle spam. We argue for separating the allocation of quotas, a relatively rare activity, from the enforcement of quotas, a frequent activity that must scale to the billions of messages sent daily. This paper tackles the quota enforcement problem, where the goal is to ensure that no sender can grossly violate its quota. The challenge is to design an enforcement scheme that is scalable, is robust against malicious attackers or participants, and preserves the privacy of communication, in a large, distributed, and untrusted environment. We discuss the design of such a system, Spam-Iam, based on a managed distributed hash table (DHT) interface, showing that it can be used in conjunction with electronic stamps (for quota allocation) to ensure that any non-negligible reuse of stamps will be detected.
The Perfect Search Engine is not Enough: a Study of Orienteering Behavior in Directed Search

Teevan, Jaime, Alvarado, Christine, Ackerman, Mark S., and Karger, David R.

CHI '04: Proceedings of the SIGCHI conference on Human factors in computing systems , 2004 (pp. 415--422)

pdf doi

Click for abstract:
This paper presents a modified diary study that investigated how people performed personally motivated searches in their email, in their files, and on the Web. Although earlier studies of directed search focused on keyword search, most of the search behavior we observed did not involve keyword search. Instead of jumping directly to their information target using keywords, our participants navigated to their target with small, local steps using their contextual knowledge as a guide, even when they knew exactly what they were looking for in advance. This stepping behavior was especially common for participants with unstructured information organization. The observed advantages of searching by taking small steps include that it allowed users to specify less of their information need and provided a context in which to understand their results. We discuss the implications of such advantages for the design of personal information management tools.
Wrapper Induction for End-User Semantic Content Development

Hogue, Andrew and Karger, David

Interaction and Design for the Semantic Web Workshop at the $13^{th}$ annual World Wide Web Conference , May 2004

Click for abstract:
The transition from existingWorld WideWeb content to the Semantic Web relies on the labeling and classification of existing information before it is useful to end-users and their agents. This paper presents a wrapper induction system designed to allow end-users to create, modify, and utilize semantic patterns on unlabeled World Wide Web documents. These patterns allow users to overlay documents with RDF classes and properties, and then to interact with this labeled content within a larger Semantic Web application, such as Haystack.
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems

Immorlica, Nicole, Karger, David, Minkoff, Maria, and Mirrokni, Vahab S.

Proceedings of the {$15^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2004 (pp. 691--700)

pdf

Click for abstract:
Combinatorial optimization is often used to "plan ahead," purchasing and allocating resources for demands that are not precisely known at the time of solution. This advance planning may be done because resources become very expensive to purchase or difficult to allocate at the last minute when the demands are known. In this work we study the tradeoffs involved in making some purchase/allocation decisions early to reduce cost while deferring others at greater expense to take advantage of additional, late-arriving information. We consider a number of combinatorial optimization problems in which the problem instance is uncertain---modeled by a probability distribution---and in which solution elements can be purchased cheaply now or at greater expense after the distribution is sampled. We show how to approximately optimize the choice of what to purchase in advance and what to defer.

2003 (22)

Koorde: A Simple Degree-Optimal Distributed Hash Table

Kaashoek, M. Frans and Karger, David R.

2nd International Workshop on Peer to Peer Systems , January 2003

ps

Click for abstract:
Koorde is a new distributed hash table (DHT) based on Chord [15] and the de Bruijn graphs [2]. While inheriting the simplicity of Chord, Koorde meets various lower bounds, such as O(log n) hops per lookup request with only 2 neighbors per node (where n is the number of nodes in the DHT), and O(log n/ log log n) hops per lookup request with O(log n) neighbors per node.
Haystack: A Platform for Authoring End-User Semantic Web Applications

Quan, Dennis, Huynh, David, and Karger, David R.

$2^{nd}$ International Semantic Web Conference , October 2003 (pp. 738--753)

download pdf

Click for abstract:
The Semantic Web promises to open innumerable opportunities for automation and information retrieval by standardizing the protocols for metadata exchange. However, just as the success of the World Wide Web can be attributed to the ease of use and ubiquity of Web browsers, we believe that the unfolding of the Semantic Web vision depends on users getting powerful but easy-to-use tools for managing their information. But unlike HTML, which can be easily edited in any text editor, RDF is more complicated to author and does not have an obvious presentation mechanism. Previous work has concentrated on the ideas of generic RDF graph visualization and RDF Schema-based form generation. In this paper, we present a comprehensive platform for constructing end user applications that create, manipulate, and visualize arbitrary RDF-encoded information, adding another layer to the abstraction cake. We discuss a programming environment specifically designed for manipulating RDF and introduce user interface concepts on top that allow the developer to quickly assemble applications that are based on RDF data models. Also, because user interface specifications and program logic are themselves describable in RDF, applications built upon our framework enjoy properties such as network updatability, extensibility, and end user customizability---all desirable characteristics in the spirit of the Semantic Web.
Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications

Stoica, Ion, Morris, Robert, Liben-Nowell, David, Karger, David R., Kaashoek, M. Frans, Dabek, Frank, and Balakrishnan, Hari

{IEEE} Transactions on Networking 11 , February 2003

pdf

Click for abstract:
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis and simulations show that Chord is scalable: communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
RDF Authoring Environments for End Users

Quan, Dennis, Huynh, David, and Karger, David R.

International Workshop on Semantic Web Foundations and Application Technologies (SWFAT) , March 2003

pdf

Click for abstract:
The Semantic Web promises to open innumerable opportunities for automation and information retrieval by standardizing the protocols for metadata exchange. However, just as the success of the World Wide Web can be attributed to the ease of use and ubiquity of Web browsers, we believe that the unfolding of the Semantic Web vision depends on users getting powerful but easy-to-use tools for managing their information. But unlike HTML, which can be easily edited in any text editor, RDF is more complicated to author and does not have an obvious presentation mechanism. Previous work has concentrated on the ideas of generic RDF graph visualization and RDF Schemabased form generation. In this paper, we present a comprehensive platform for constructing end user applications that create, manipulate, and visualize arbitrary RDF-encoded information, adding another layer to the abstraction cake. We discuss a programming environment specifically designed for manipulating RDF and introduce user interface concepts on top that allow the developer to quickly assemble applications that are based on RDF data models. Also, because user interface specifications and program logic are themselves describable in RDF, applications built upon our framework enjoy properties such as network updatability, extensibility, and end user customizability ? all desirable characteristics in the spirit of the Semantic Web.
A Unified Abstraction for Messaging on the Semantic Web

Quan, Dennis, Bakshi, Karun, and Karger, David R.

Developers' day, $12^{th}$ International World Wide Web Conference , May 2003 (pp. 231)

Click for abstract:
Since its inception, the Internet has been a hotbed of several successful communications channels, starting off with e-mail, Internet Relay Chat and Usenet newsgroups and more recently adding Web annotation, instant messaging, and news feeds. However, these channels were developed fairly independently, and in many cases their respective functionalities have grown to overlap significantly. For instance, users of these systems have separate identifiers for e-mail, chat, and instant messaging, and clients for these systems all have their own implementations of threaded message views. We believe these problems stem from a lack of a common user interface and data model. In this paper we use basic concepts from the Semantic Web and RDF to unify and model these seemingly disparate messaging paradigms. We also demonstrate a generalized user interface for messaging that uses the data model we have developed. From this process we realize a number of synergies that result from the reduction of overlap and the finer-grained control users are given over message composition, transmission, storage and retrieval.
User Interfaces for Supporting Multiple Categorization.

Quan, Dennis, Bakshi, Karun, Huynh, David, and Karger, David R.

INTERACT: $9^{th}$ IFIP International Conference on Human Computer Interaction , September 2003 (pp. 228--235)

pdf

Click for abstract:
As the amount of information stored on and accessed by computer has increased over the past twenty years, the tools available for organizing and retrieving such information have become outdated. The folder paradigm has dominated existing user interfaces as the primary mechanism for organizing information for day-to-day use. This paradigm encourages many-to-one placement of documents into strictly hierarchical containers. In this paper we examine an alternative organization and navigation mechanism that promotes membership in multiple overlapping categories (as opposed to storage containment). In particular, we explore the user interface consequences of multiple categorization support being made conveniently available from within Web browsers. We have carried out user studies providing evidence that compared to the folder paradigm, multiple categorization not only improves organization and retrieval times but also matches more closely with the way users naturally think about organizing their information.
Haystack: A Platform for Creating, Organizing, and Visualizing Semistructured Information

Huynh, David, Karger, David R., and Quan, Dennis

Intelligent User Interfaces , January 2003 Demo

pdf
Sticky Notes for the Semantic Web

Karger, David R., Katz, Boris, Lin, Jimmy, and Quan, Dennis

Intelligent User Interfaces , January 2003 (pp. 254--256) Poster

download pdf
Empirical Development of an Exponential Probabilistic Model for Text Retrieval

Teevan, Jaime and Karger, David R.

$26^{th}$ Internationl ACM SIGIR Conference , July 2003

pdf

Click for abstract:
Much work in information retrieval focuses on using a model of documents and queries to derive retrieval algorithms. Model based development is a useful alternative to heuristic development because in a model the assumptions are explicit and can be examined and refined independent of the particular retrieval algorithm. We explore the explicit assumptions underlying the na?ve framework by performing computational analysis of actual corpora and queries to devise a generative document model that closely matches text. Our thesis is that a model so developed will be more accurate than existing models, and thus more useful in retrieval, as well as other applications. We test this by learning from a corpus the best document model. We find the learned model better predicts the existence of text data and has improved performance on certain IR tasks.
Tackling the Poor Assumptions of Naive Bayes Text Classifiers

Rennie, Jason D. M., Shih, Lawrence, Teevan, Jaime, and Karger, David R.

The Twentieth International Conference on Machine Learning , August 2003

download pdf ps.gz

Click for abstract:
Naive Bayes is often used as a baseline in text classification because it is fast and easy to implement. Its severe assumptions make such efficiency possible but also adversely affect the quality of its results. In this paper we propose simple, heuristic solutions to some of the problems with Naive Bayes classifiers, addressing both systemic issues as well as problems that arise because text is not actually generated according to a multinomial model. We find that our simple corrections result in a fast algorithm that is competitive with stateof- the-art text classification algorithms such as the Support Vector Machine.
Empirical Development of an Exponential Probabilistic Model for Text Retrieval: Using Textual Analysis to Build a Better Model

Teevan, Jaime and Karger, David R.

$26^{th}$ Internationl ACM SIGIR Conference , July 2003

pdf ps

Click for abstract:
Much work in information retrieval focuses on using a model of documents and queries to derive retrieval algorithms. Model based development is a useful alternative to heuristic development because in a model the assumptions are explicit and can be examined and refined independent of the particular retrieval algorithm. We explore the explicit assumptions underlying the na?ve framework by performing computational analysis of actual corpora and queries to devise a generative document model that closely matches text. Our thesis is that a model so developed will be more accurate than existing models, and thus more useful in retrieval, as well as other applications. We test this by learning from a corpus the best document model. We find the learned model better predicts the existence of text data and has improved performance on certain IR tasks.
Approximation Algorithms for Orienteering and Discounted-Reward TSP

Blum, Avrim, Chawla, Shuchi, Karger, David R., Lane, Terran, Meyerson, Adam, and Minkoff, Maria

Proceedings of the {$36^{th}$} Annual Symposium on the Foundations of Computer Science , October 2003 Journal version appears in SIAM Journal on Computing 37(2)

ps

Click for abstract:
In this paper, we give the first constant-factor approximation algorithm for the rooted ORIENTEERING problem, as well as a new problem that we call the DISCOUNTED-REWARD-TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and rewards on nodes, and a start node s. In the ORIENTEERING problem, the goal is to find a path starting at s that maximizes the reward collected, subject to a hard limit on the total length of the path. In the DISCOUNTEDREWARD- TSP, instead of a length limit we are given a discount factor ?, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by ?t. This problem is motivated by an approximation to a planning problem in theMarkov decision process (MDP) framework under the commonly employed infinite horizon discounted reward optimality criterion. The approximation arises from a need to deal with exponentially large state spaces that emerge when trying to model one-time events and non-repeatable rewards (such as for package deliveries). We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted ORIENTEERING problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem [3, 1]. We complement our approximation result for ORIENTEERING by showing that the problem is APX-hard.
On the Feasibility of Peer-to-Peer Web Indexing and Search

Li, Jinyang, Loo, Book Thau, Hellerstein, Joe, Kaashoek, M. Frans, Karger, David R., and Morris, Robert

2nd International Workshop on Peer to Peer Systems , January 2003 (pp. 207--215)

pdf

Click for abstract:
This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an overlay network (as in Gnutella), and intersection of index lists stored in a distributed hash table. We present a simple feasibility analysis based on the resource constraints and search workload. Our study suggests that the peer-to-peer network does not have enough capacity to make naive use of either of search techniques attractive for Web search. The paper presents a number of existing and novel optimizations for P2P search based on distributed hash tables, estimates their effects on performance, and concludes that in combination these optimizations would bring the problem to within an order of magnitude of feasibility. The paper suggests a number of compromises that might achieve the last order of magnitude.
LP Decoding

Feldman, Jon, Karger, David R., and Wainwright, Martin J.

Proceedings of the 41st Annual Allerton Conference on Communication, Control, and Computing , October 2003

pdf ps.gz

Click for abstract:
Linear programming (LP) relaxation is a common technique used to find good solutions to complex optimization problems. We present the method of ?LP decoding?: applying LP relaxation to the problem of maximum-likelihood (ML) decoding. An arbitrary binary-input memoryless channel is considered. This treatment of the LP decoding method places our previous work on turbo codes [6] and low-density parity-check (LDPC) codes [8] into a generic framework. We define the notion of a proper relaxation, and show that any LP decoder that uses a proper relaxation exhibits many useful properties. We describe the notion of pseudocodewords under LP decoding, unifying many known characterizations for specific codes and channels. The fractional distance of an LP decoder is defined, and it is shown that LP decoders correct a number of errors equal to half the fractional distance. We also discuss the application of LP decoding to binary linear codes. We define the notion of a relaxation being symmetric for a binary linear code. We show that if a relaxation is symmetric, one may assume that the all-zeros codeword is transmitted.
On Randomized Network Coding

Ho, Tracey, M\'{e}dard, Muriel, Shi, J., Effros, Michelle, and Karger, David R.

$41^{st}$ Allerton Annual Conference on Communication, Control, and Signal Processing , 2003 Invited paper

pdf

Click for abstract:
We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links over some field. This approach was first described in [3], which gave, for acyclic delay-free networks, a bound on error probability, in terms of the number of receivers and random coding output links, that decreases exponentially with code length. The proof was based on a result in [2] relating algebraic network coding to network flows. In this paper, we generalize these results to networks with cycles and delay. We also show, for any given acyclic network, a tighter bound in terms of the probability of connection feasibility in a related network problem with unreliable links. From this we obtain a success probability bound for randomized network coding in link-redundant networks with unreliable links, in terms of link failure probability and amount of redundancy.
The Benefits of Network Coding over Routing in a Randomized Setting

Ho, Tracey, Koetter, Ralf, M\'edard, Muriel, Karger, David R., and Effros, Michelle

IEEE International Symposium on Information Theory , June 2003

pdf

Click for abstract:
We present a novel randomized network coding approach for robust, distributed transmission and compression of information in networks, and demonstrate its advantages over routing-based approaches.
Network Coding from a Network Flow Perspective

Ho, Tracey, Karger, David R., M\'{e}dard, Muriel, and Koetter, Ralf

IEEE International Symposium on Information Theory , June 2003

pdf

Click for abstract:
We make precise connections between algebraic network coding and network flows. Our combinatorial formulations offer new insights, mathe- matical simplicity, and lead to a substantially tighter upper bound on the coding field size required for a given connection problem than that in [5].
User Interface Continuations

Quan, Dennis, Huynh, David, Karger, David R., and Miller, Robert

The $16^{th}$ Annual Symposium on User Interface Software and Technology , November 2003

pdf

Click for abstract:
Dialog boxes that collect parameters for commands often create ephemeral, unnatural interruptions of a program?s normal execution flow, encouraging the user to complete the dialog box as quickly as possible in order for the program to process that command. In this paper we examine the idea of turning the act of collecting parameters from a user into a first class object called a user interface continuation. Programs can create user interface continuations by specifying what information is to be collected from the user and supplying a callback (i.e., a continuation) to be notified with the collected information. A partially completed user interface continuation can be saved as a new command, much as currying and partially evaluating a function with a set of parameters produces a new function. Furthermore, user interface continuations, like other continuation-passing paradigms, can be used to allow program execution to continue uninterrupted while the user determines a command?s parameters at his or her leisure.
Looking up data in P2P systems

Balakrishnan, Hari, Kaashoek, M. Frans, Karger, David, Morris, Robert, and Stoica, Ion

Communications of the ACM , February 2003

pdf

Click for abstract:
The main challenge in P2P computing is to design and implement a robust and scalable distributed system composed of inexpensive, individually unreliable computers in unrelated administrative domains. The participants in a typical P2P system might include computers at homes, schools, and businesses, and can grow to several million concurrent participants.
Using Linear Programming to Decode Linear Codes

Feldman, Jon, Karger, David, and Wainwright, Martin

37th annual Conference on Information Sciences and Systems (CISS) , March 2003

pdf ps.gz

Click for abstract:
Given a linear code and observations from a noisy channel, the decoding problem is to de- termine the most likely (ML) codeword. We describe a method for approximate ML decoding of an arbi- trary binary linear code, based on a linear program- ming (LP) relaxation that is defined by a factor graph or parity check representation of the code. The result- ing LP decoder, which generalizes our previous work on turbo-like codes [FK02, FWK02], has the ML cer- tificate property: it either outputs the ML codeword with a guarantee of correctness, or acknowledges an error. We provide a precise characterization of when the LP decoder succeeds, based on the cost of pseu- docodewords associated with the factor graph. We in- troduce the notion of the fractional distance of a code, defined with respect to a particular LP relax- ation, and prove that the LP decoder will correct up to $()$ errors. For the BEC, we prove that the performance of LP decoding is equivalent to standard iterative decoding.
On Coding for Non-Multicast Networks

M\'{e}dard, Muriel, Effros, Michelle, Ho, Tracey, and Karger, David

$41^{st}$ Allerton Annual Conference on Communication, Control, and Signal Processing , 2003 Invited paper

pdf

Click for abstract:
We consider the issue of coding for non-multicast networks. For multicast networks, it is known that linear operations over a field no larger than the number of receivers are sufficient to achieve all feasible connections. In the case of nonmulticast networks, necessary and sufficient conditions are known, if we restrict ourselves to linear codes over a finite field [1]. However, no linearity sufficiency results exist for non-multicast networks. Indeed, [2] shows that linearity over a field is not sufficient in general. We present a coding theorem that provides necessary and sufficient conditions, in terms of receiver entropies, for an arbitrary set of connections to be achievable on any network. We conjecture that linearity is sufficient to satisfy the coding theorem, when linear operations are performed over vectors rather than scalars in a field. We illustrate the intuition of this conjecture with an example. This work is part of an ongoing cooperation with R. Koetter.
Linear Network Codes: A Unified Framework for Source, Channel, and Network Coding

Effros, Michelle, M\'{e}dard, Muriel, Ho, Tracey, Ray, S., Karger, David, Koetter, Ralf, and Hassibi, B.

DIMACS workshop on network information theory , 2003 Invited Paper

pdf

Click for abstract:
We examine the issue of separation and code design for network data transmission environments. We demonstrate that source-channel sep- aration holds for several canonical network channel models when the whole network operates over a common ?nite ?eld. Our approach uses linear codes. This simple, unifying framework allows us to re-establish with economy the optimality of linear codes for single transmitter channels and for Slepian-Wolf source coding. It also enables us to establish the optimality of linear codes for multiple access channels and for erasure broadcast channels. Moreover, we show that source-channel separation holds for these networks. This robustness of separation we show to be strongly predicated on the fact that noise and inputs are independent. The linearity of source, channel, and network coding blurs the delineation between these codes, and thus we explore joint linear de- sign. Finally, we illustrate the fact that design for individual network modules may yield poor results when such modules are concatenated, demonstrating that end-to-end coding is necessary. Thus, we argue, it is the lack of decom- posability into canonical network modules, rather than the lack of separation between source and channel coding, that presents major challenges for coding in networks.

2002 (10)

Finding Nearest Neighbors in Growth Restricted Metrics

Karger, David R. and Ruhl, Matthias

Proceedings of the {$33^{rd}$} {ACM} Symposium on Theory of Computing , May 2002 (pp. 741--750)

ps ps.gz

Click for abstract:
Most research on nearest neighbor algorithms in the literature has been focused on the Euclidian case. In many practical search problems however, the underlying metric cannot be well approximated by an Euclidian space, and applying general purpose algorithms result in poor performance by not making use of the special properties of the subspace that the points lie in. In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point $q$ the number of points within a radius $2r$ around $q$ is at most a constant times the number of points within radius $r$. Spaces of this kind occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.
Analysis of the Evolution of Peer to Peer Systems

Liben-Nowell, David, Balakrishnan, Hari, and Karger, David R.

ACM Symposium on Principles of Distributed Computing , July 2002 (pp. 233--242)

pdf ps

Click for abstract:
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a distributed hash table abstraction, and study the process by which Chord maintains its distributed state as nodes join and leave the system. We argue that traditional performance measures based on run-time are uninformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric. We give a general lower bound on this rate for a network to remain connected, and prove that an appropriately modified version of Chord's maintenance rate is within a logarithmic factor of the optimum rate.
Observations on the Dynamic Evolution of Peer to Peer Systems

Liben-Nowell, David, Balakrishnan, Hari, and Karger, David R.

Proceedings of the First International Workshop on Peer-to-Peer Systems , March 2002

Click for abstract:
A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate for an infinite time, performance measures based on runtime are uninformative; instead, we must study the rate at which nodes consume resources in order to maintain the system state. This ?maintenance bandwidth? depends on the rate at which nodes tend to enter and leave the system. In this paper, we formalize this dependence. Having done so, we analyze the Chord peer-to-peer protocol. We show that Chord's maintenance bandwidth to handle concurrent node arrivals and departures is near optimal, exceeding the lower bound by only a logarithmic factor. We also outline and analyze an algorithm that converges to a correct routing state from an arbitrary initial condition.
Random Sampling from Residual Graphs

Karger, David R. and Levine, Matthew S.

Proceedings of the {$33^{rd}$} {ACM} Symposium on Theory of Computing , May 2002 (pp. 63--66)

ps ps.gz

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

Feldman, Jon and Karger, David R.

Proceedings of the {$35^{th}$} Annual Symposium on the Foundations of Computer Science , November 2002

pdf ps.gz doi

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

Feldman, Jon, Karger, David R., and Wainwright, Martin J.

Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing , October 2002

pdf ps.gz

Click for abstract:
In recent work (Feldman and Karger [8]), we introduced a new approach to decoding turbo-like codes based on linear programming (LP). We gave a precise characterization of the noise patterns that cause decoding error under the binary symmetric and additive white Gaussian noise channels. We used this characterization to prove that the word error rate is bounded by an inverse polynomial in the code length. Furthermore, for any turbo-like code, our algorithm has the ML certificate property: whenever it outputs a code word, it is guaranteed to be the maximum-likelihood (ML) code word. In this paper we extend these results and give an iterative decoder whose output is equivalent to that of the LP decoder. We also extend the MLcertificate property to the more efficient iterative tree reweighted max-product message-passing algorithm developed by Wainwright, Jaakkola, and Willsky [13]: we show that whenever this algorithm converges to a code word, it must be the ML code word. Finally, we demonstrate experimentally that the noise patterns that cause decoding error in the LP decoder also cause decoding error in the standard iterative sum-product and max-product (min-sum) message-passing algorithms. Consequently, the deterministically constructible interleaver used by the LP decoder to achieve its bounds on error rate is useful in practice not only for the LP decoder, but for these standard iterative decoders as well.
INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery

Balazinska, Magdalena, Balakrishnan, Hari, and Karger, David

Proceedings of the International Conference on Pervasive Computing (Pervasive 2002) , August 2002

pdf

Click for abstract:
The decreasing cost of computing technology is speeding the deployment of abundant ubiquitous computation and communication.
Haystack: A Platform for Creating, Organizing, and Visualizing Information Using {RDF}

Huynh, David, Karger, David, and Quan, Dennis

Semantic Web Workshop at WWW2002 , May 2002

pdf

Click for abstract:
The Resource Definition Framework (RDF) is designed to support agent communication on the Web, but it is also suitable as a framework for modeling and storing personal information. Haystack is a personalized information repository that employs RDF in this manner. This flexible semistructured data model is appealing for several reasons. First, RDF supports ontologies created by the user and tailored to the user?s needs. At the same time, system ontologies can be specified and evolved to support a variety of high-level functionalities such as flexible organization schemes, semantic querying, and collaboration. In addition, we show that RDF can be used to engineer a component architecture that gives rise to a semantically rich and uniform user interface. We demonstrate that by aggregating various types of users? data together in a homogeneous representation, we create opportunities for agents to make more informed deductions in automating tasks for users. Finally, we discuss the implementation of an RDF information store and a programming language specifically suited for manipulating RDF.
Infranet: Circumventing Web Censorship and Surveillance

Feamster, Nick, Balazinska, Magdalena, Harfst, Greg, Balakrishnan, Hari, and Karger, David

Proceedings of the $11^{th}$ USENIX Security Symposium , August 2002 (pp. 247--262) Best Student Paper Award

pdf ps ps.gz

Click for abstract:
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to surreptitiously retrieve sensitive content via cooperating Web servers distributed across the global Internet. These Infranet servers provide clients access to censored sites while continuing to host normal uncensored content. Infranet uses a tunnel protocol that provides a covert communication channel between its clients and servers, modulated over standard HTTP transactions that resemble innocuous Web browsing. In the upstream direction, Infranet clients send covert messages to Infranet servers by associating meaning to the sequence of HTTP requests being made. In the downstream direction, Infranet servers return content by hiding censored data in uncensored images using steganographic techniques. We describe the design, a prototype implementation, security properties, and performance of Infranet. Our security analysis shows that Infranet can successfully circumvent several sophisticated censoring techniques.
Basic Concepts for Managing Semi-structured Information in Haystack

Quan, Dennis, Huynh, David F., Sinha, Vineet, Zhurakhinskaya, Marina, and Karger, David

2nd Annual Student Oxygen Workshop, Gloucester, MA, USA , 2002

2001 (12)

Internet Surveillance of Pro-drug Websites. I. Incidence of Club Drug Reporting Over a One-Year Period.

Boyer, Edward W., Shih, Kai, Karger, David R., Quang, L., and Case, P.

Journal of Toxicology: Clinical Toxicology 39 , 2001 (pp. 536) (abstract)
Internet Surveillance of Pro-drug Websites. II. Identification of Emerging Drug Use Trends.

Boyer, Edward W., Shih, Kai, Karger, David R., Quang, L., and Case, P.

Journal of Toxicology: Clinical Toxicology 39 , 2001 (pp. 537) (abstract)
Internet Surveillance of Pro-drug Websites. III. Identification of Emerging Drugs of Abuse.

Boyer, Edward W., Shih, Kai, Karger, David R., Quang, L., and Case, P.

Journal of Toxicology: Clinical Toxicology 39 , 2001 (pp. 537) (abstract)
Random Sampling in Graph Optimization Problems: A Survey

Karger, David R.

in S. Rajasekaran and P. Pardalos and J.H. Reif and J. Rolim, editors, Handbook on Randomization , 2001

ps ps.gz

Click for abstract:
Randomization has become a pervasive technique in combinatorial optimization. We survey our thesis and subsequent work, which uses four common randomization techniques to attack numerous optimization problems on undirected graphs. 1 Introduction Randomization has become a pervasive technique in combinatorial optimization. Randomization has been used to develop algorithms that are faster, simpler, and/or better-performing than previous deterministic algorithms.
An Experimental Study of Polylogarithmic Fully-Dynamic Connectivity Algorithms

Iyer, Raj D., Karger, David R., Rahul, Hariharan, and Thorup, Mikkel

ACM Journal of Experimental Algorithmics , 2001 Special issue of papers selected from ALENEX 2000

Click for abstract:
We present an experimental study of different variants of the amortized O(log2 n)-time fully-dynamic connectivity algorithm of Holm, de Lichtenberg, and Thorup (STOC'98). The experiments build upon experiments provided by Alberts, Cattaneo, and Italiano (SODA'96) on the randomized amortized O(log3 n) fully-dynamic connectivity algorithm of Henzinger and King (STOC'95). Our experiments shed light upon similarities and differences between the two algorithms. We also present a slightly modified version of the Henzinger-King algorithm that runs in O(log2 n) time, which resulted from our experiments.
Scheduling Trees with Communication and Precedence Delays

Engels, Daniel W., Feldman, Jon, Karger, David R., and Ruhl, Matthias

Proceedings of the {$12^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2001

ps
Learning Markov Networks: Maximum Bounded Tree-width Graphs

Karger, David R. and Srebro, Nati

Proceedings of the {$12^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 2001 (pp. 392--401)

ps.gz

Click for abstract:
Markov networks are a common class of graphical models used in machine learning. Such models use an undirected graph to capture dependency information among random variables in a joint probability distribution. Once one has chosen to use a Markov network model, one aims to choose the model that ?best explains? the data that has been observed?this model can then be used to make predictions about future data. We show that the problem of learning a maximum likelihood Markov network given certain observed data can be reduced to the problem of identifying a maximum weight low-treewidth graph under a given input weight function. We give the first constant factor approximation algorithm for this problem. More precisely, for any fixed treewidth objective k, we find a treewidth-k graph with an f(k) fraction of the maximum possible weight of any treewidth-k graph.
A Randomized Fully Polynomial Approximation Scheme for the All Terminal Network Reliability Problem

Karger, David R.

SIAM Review 43 (3) , 2001 (pp. 499--522) A preliminary version appeared in Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing. This corrects a version published in SICOMP Winner, SIAM Outstanding Paper Prize, 2000

ps

Click for abstract:
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is ?P-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and 1/e an estimate for the failure probability that is accurate to within a relative error of 1 ? e with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492-514].
Wide-area cooperative storage with CFS

Dabek, Frank, Kaashoek, M. Frans, Karger, David, Morris, Robert, and Stoica, Ion

Proceedings of the {ACM} 2001 Symposium on Operating System Principles , October 2001

pdf

Click for abstract:
The Cooperative File System (CFS) is a new peer-to-peer read-only storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS does this with a completely decentralized architecture that can scale to large systems. CFS servers provide a distributed hash table (DHash) for block storage. CFS clients interpret DHash blocks as a file system. DHash distributes and caches blocks at a fine granularity to achieve load balance, uses replication for robustness, and decreases latency with server selection. DHash finds blocks using the Chord location protocol, which operates in time logarithmic in the number of servers.CFS is implemented using the SFS file system toolkit and runs on Linux, OpenBSD, and FreeBSD. Experience on a globally deployed prototype shows that CFS delivers data to clients as fast as FTP. Controlled tests show that CFS is scalable: with 4,096 servers, looking up a block of data involves contacting only seven servers. The tests also demonstrate nearly perfect robustness and unimpaired performance even when as many as half the servers fail.
Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service

Dabek, Frank, Brunskill, Emma, Kaashoek, M. Frans, Karger, David, Morris, Robert, Stoica, Ion, and Balakrishnan, Hari

Proceedings of the 8th {W}orkshop on {H}ot {T}opics in {O}perating {S}ystems ({HotOS-VIII}) , May 2001

ps

Click for abstract:
We argue that the core problem facing peer-to-peer systems is locating documents in a decentralized network and propose Chord, a distributed lookup primitive. Chord provides an efficient method of locating documents while placing few constraints on the applications that use it. As proof that Chord?s functionality is useful in the development of peer-to-peer applications, we outline the implementation of a peer-to-peer file sharing system based on Chord.
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Stoica, Ion, Morris, Robert, Karger, David, Kaashoek, M. Frans, and Balakrishnan, Hari

Proceedings of the {ACM} {SIGCOMM} '01 Conference , August 2001 (pp. 149--160)

ps

Click for abstract:
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
Learning Classes Correlated to a Hierarchy

Shih, Lawrence and Karger, David

Technical report , 2001

Click for abstract:
Trees are a common way of organizing large amounts of information by placing items with similar characteristics near one another in the tree. We introduce a classification problem where a given tree structure gives us information on the best way to label nearby elements. We suggest there are many practical problems that fall under this domain. We propose a way to map the classification problem onto a standard Bayesian inference problem. We also give a fast, specialized inference algorithm that incrementally updates relevant probabilities. We apply this algorithm to web-classification problems and show that our algorithm empirically works well.

2000 (6)

Dynamic Graph Algorithms with Applications

Thorup, Mikkel and Karger, David R.

Seventh Scandinavian Workshop on Algorithm Theory , July 2000

Click for abstract:
First we review amortized fully-dynamic polylogarithmic algorithms for connectivity, minimum spanning trees (MST), 2-edge- and biconnectivity. Second we discuss how they yield improved static algorithms: connectivity for constructing a tree from homeomorphic subtrees, 2-edge connectivity for finding unique matchings in graphs, and MST for packing spanning trees in graphs. The application of MST for spanning tree packing is new and when boot-strapped, it yields a fully-dynamic polylogarithmic algorithm for approximating general edge connectivity within a factor ?{2+o(1)}. Finally, on the more practical side, we will discuss how output sensitive algorithms for dynamic shortest paths have been applied successfully to speed up local search algorithms for improving routing on the internet, roughly doubling the capacity.
Augmenting Undirected Edge Connectivity in {$\Olog(n^2)$} Time

Bencz{\'u}r, Andr{\'a}s A. and Karger, David R.

Journal of Algorithms 37 , 2000 (pp. 2--36) Special issue of selected papers from Proceedings of the {$9^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms

ps

Click for abstract:
We give improved randomized (Monte Carlo) algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time ~ O(n^2) on n-vertex graphs, making them an ~\Omega(m/n) factor faster than the best known deterministic ones on m-edge graphs.
A Scalable Location Service for Geographic Ad-Hoc Routing

Li, Jinyang, Janotti, John, Couto}, Douglas S. J. {De, Karger, David R., and Morris, Robert

Proceedings of the $6^{th}$ {ACM} International Conference on Mobile Computing and Networking ({MobiCom} 2000) , August 2000 (pp. 120--130)

pdf ps

Click for abstract:
GLS is a new distributed location service which tracks mobile node locations. GLS combined with geographic forwarding allows the construction of ad hoc mobile networks that scale to a larger number of nodes than possible with previous work. GLS is decentralized and runs on the mobile nodes themselves, requiring no fixed infrastructure. Each mobile node periodically updates a small set of other nodes (its location servers) with its current location. A node sends its position updates to its location servers without knowing their actual identities, assisted by a predefined ordering of node identifiers and a predefined geographic hierarchy. Queries for a mobile node's location also use the predefined identifier ordering and spatial hierarchy to find a location server for that node. Experiments using the ns simulator for up to 600 mobile nodes show that the storage and bandwidth requirements of GLS grow slowly with the size of the network. Furthermore, GLS tolerates node failures well: each failure has only a limited effect and query performance degrades gracefully as nodes fail and restart. The query performance of GLS is also relatively insensitive to node speeds. Simple geographic forwarding combined with GLS compares favorably with Dynamic Source Routing (DSR): in larger networks (over 200 nodes) our approach delivers more packets, but consumes fewer network resources.
Minimum Cuts in Near-Linear Time

Karger, David R.

Journal of the ACM 47 (1) , January 2000 (pp. 46--76) A preliminary version appeared in Proceedings of the {$28^{th}$} {ACM} Symposium on Theory of Computing

ps

Click for 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.
An Experimental Study of Polylogarithmic Fully-Dynamic Connectivity Algorithms

Iyer, Raj D., Karger, David R., Rahul, Hariharan, and Thorup, Mikkel

Proceedings of ALENEX00: Workshop on Algorithm Engineering and Experimentation , January 2000 ALENEX00 special issue of the Journal of Experimental Algorithmics

ps

Click for abstract:
We present an experimental study of different variants of the amortized O(log2 n)-time fully-dynamic connectivity algorithm of Holm, de Lichtenberg, and Thorup (STOC'98). The experiments build upon experiments provided by Alberts, Cattaneo, and Italiano (SODA'96) on the randomized amortized O(log3 n) fully-dynamic connectivity algorithm of Henzinger and King (STOC'95). Our experiments shed light upon similarities and differences between the two algorithms. We also present a slightly modified version of the Henzinger-King algorithm that runs in O(log2 n) time, which resulted from our experiments.
Building Routing Trees with Incomplete Global Knowledge

Karger, David R. and Minkoff, Maria

Proceedings of the {$33^{rd}$} Annual Symposium on the Foundations of Computer Science , November 2000 (pp. 613--623)

ps

1999 (9)

Fast Connected Components Algorithms for the {EREW} {PRAM}

Karger, David R., Nisan, Noam, and Parnas, Michal

SIAM Journal on Computing 28 (3) , 1999 (pp. 1021--1034) A preliminary version appeared in Proceedings of the {$4^{th}$} Annual {ACM}-{SIAM} Symposium on Parallel Algorithms and Architectures

ps
Polynomial Time Approximation Schemes for Dense Instances of {$\NP$}-Hard Problems

Arora, Sanjeev, Karger, David R., and Karpinski, Marek

Journal of Computer and System Sciences 58 , 1999 (pp. 193--210) Special issue of selected papers from Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing
Haystack: Per-User Information Environments

Adar, Eytan, Karger, David R., and Stein, Lynn Andrea

Proceedings of the 8th International Conference on Information and Knowledge Management , November 1999 (pp. 413--422)

pdf ps ps.gz

Click for abstract:
Traditional Information Retrieval (IR) systems are designed to provide uniform access to centralized corpora by large numbers of people. The Haystack project emphasizes the relationship between a particular individual and his corpus. An individual's own haystack priviliges information with which that user interacts, gathers data about those interactions, and uses this metadata to further personalize the retrieval process. This paper describes the prototype Haystack system.
Optimal Rounding Algorithms for a Geometric Embedding of the Multiway Cut Problem

Karger, David R., Klein, Philip N., Stein, Clifford, Thorup, Mikkel, and Young, Neal

Proceedings of the {$30^{th}$} {ACM} Symposium on Theory of Computing , May 1999 (pp. 668--677)

ps

Click for abstract:
Given an undirected graph with edge costs and a subset of k 2 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, end Rabbi (STOC?98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (312 - l/k)-approximation algorithm. In this paper. we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12/11. giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12/11 and give an algorithm that finds a cut of value 12/11 times the relaxation value. This is the best possible perfom~ance guarantee for any algorithm based purely on the value of the relaxation and improves on Calinescu et al.?s factor of 716. We also improve the upper hounds for all larger values of k. Fork = 4,5, our best upper bounds are based on computer constructed and analyzed rounding schemes, while fork > 6 we give an algorithm with performance ratio 1.3438 - a. Our results were discovered with the help of computational experiments that we also describe here.
A Randomized Fully Polynomial Approximation Scheme for the All Terminal Network Reliability Problem

Karger, David R.

SIAM Journal on Computing 29 (2) , 1999 (pp. 492--514) A preliminary version appeared in Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing. A corrected version was published in SIAM Review 43(3) Winner, SIAM Outstanding Paper Prize, 2000

ps

Click for abstract:
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is $\SP$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described.
Random Sampling in Cut, Flow, and Network Design Problems

Karger, David R.

Mathematics of Operations Research 24 (2) , May 1999 (pp. 383--413) A preliminary version appeared in Proceedings of the {$26^{th}$} {ACM} Symposium on Theory of Computing

ps

Click for abstract:
We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to [math not displayed].
Web Caching with Consistent Hashing

Karger, David, Sherman, Alex, Berkheimer, Andy, Bogstad, Bill, Dhanidina, Rizwan, Iwamoto, Ken, Kim, Brian, Matkins, Luke, and Yerushalmi, Yoav

Proceedings of the Eighth World-Wide Web Conference , May 1999

download
{Web} caching with consistent hashing

Karger, David, Sherman, Alex, Berkheimer, Andy, Bogstad, Bill, Dhanidina, Rizwan, Iwamoto, Ken, Kim, Brian, Matkins, Luke, and Yerushalmi, Yoav

Computer Networks 31 (11--16) , May 1999 (pp. 1203--1213)

download

Click for abstract:
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.
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

Afrati, Foto, Bampis, Evripidis, Chekuri, Chandra, Karger, David, Kenyon, Claire, Khanna, Sanjeev, Milis, Ioannis, Queyranne, Maurice, Skutella, Martin, Stein, Cliff, and Sviridenko, Maxim

Proceedings of the {$32^{nd}$} Annual Symposium on the Foundations of Computer Science , October 1999 (pp. 32--43)

ps

Click for abstract:
We consider the problem of scheduling jobs with release dates on parallel machines so as to minimize average weighted completion time. While constant factor approximation algorithms for many variants have been developed in the last few years, we present the first known polynomial time approximation schemes for several of them. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our PTASs are also efficient. For most variants, the running time for a (1+e)-approximation on an instance with n jobs and m machines is O(nlog n) for each fixed e, and for all variants the running time's dependence on n is a fixed polynomial whose degree is independent of e and m.

1998 (9)

Random Sampling in Graph Optimization Problems: A Survey

Karger, David R.

Optima 58 , 1998 (pp. 1--11)

pdf

Click for abstract:
Randomization has become a pervasive technique in combinatorial optimization. We survey our thesis and subsequent work, which uses four common randomization techniques to attack numerous optimization problems on undirected graphs.
Augmenting Undirected Edge Connectivity in {$\Olog(n^2)$} Time

Bencz{\'u}r, Andr{\'a}s A. and Karger, David R.

Proceedings of the {$9^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1998 (pp. 500--509) Journal version appears in Journal of Algorithms 37

ps

Click for abstract:
We give improved randomized algorithms for the undirected edge splitting and connectivity augmentation problems. Our algorithms are an approximately $O()$ factor faster than the best known deterministic ones. Our runtimes of $O()$ are near-optimal in the sense that even for sparse input graphs the optimum output graph may require $\Omega()$ edges.
Approximate Graph Coloring by Semidefinite Programming

Karger, David R., Motwani, Rajeev, and Sudan, Madhu

Journal of the ACM 45 (2) , March 1998 (pp. 246--265) A preliminary version appeared in Proceedings of the {$35^{th}$} Annual Symposium on the Foundations of Computer Science

ps

Click for abstract:
We consider the problem of coloring 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(n1/4 log1/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 k-colorable graphs to obtain a coloring using min{O(&Dgr;1-2/k log1/2 &Dgr; log n), O(n1-3/(k+1) log1/2 n)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lov?sz &thgr;-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 &thgr;-function.
Random Sampling and Greedy Sparsification in Matroid Optimization Problems

Karger, David R.

Mathematical Programming {B} 82 (1--2) , June 1998 (pp. 41--81) A preliminary version appeared in Proceedings of the {$34^{th}$} Annual Symposium on the Foundations of Computer Science

ps

Click for abstract:
Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Applications of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by a greedy algorithm that grows an independent set into an the optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a given fixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems.
Techniques for Scheduling with Rejection

Engels, Daniel W., Karger, David R., Kolliopoulos, S. G., Sengupta, S., Uma, R. N., and Wein, Joel

European Symposium on Algorithms (Lecture Notes in Computer Science) 1461 , 1998 (pp. 490)

ps

Click for abstract:
We consider the general problem of scheduling a set of jobs where we may choose not to schedule certain jobs, and thereby incur a penalty for each rejected job. More specifically, we focus on choosing a set of jobs to reject and constructing a schedule for the remaining jobs so as to optimize the sum of the weighted completion times of the jobs scheduled plus the sum of the penalties of the jobs rejected. We give several techniques for designing scheduling algorithms under this criterion. Many of these techniques show how to reduce a problem with rejection to a (potentially more complex) scheduling problem without re- jection. Some of the reductions are based on general properties of certain kinds of linear-programming relaxations of optimization problems, and therefore are applicable to problems outside of scheduling; we demon- strate this by giving an approximation algorithm for a variant of the facility-location problem. In the last section of the paper we consider a different notion of rejec- tion in the context of scheduling: scheduling jobs with due dates so as to maximize the number of jobs that complete by their due dates, or equivalently to minimize the number of jobs that do not complete by their due date and that thus can be considered \rejected." We inves- tigate the approximability of a simple version of this problem, giving approximation algorithms and characterizing integrality gaps of a class of linear-programming relaxations.
Scheduling Algorithms

Karger, David R., Stein, Clifford, and Wein, Joel

in Mikhail J. Atallah, editors, Algorithms and Theory of Computation Handbook , 1998
Better Random Sampling Algorithms for Flows in Undirected Graphs

Karger, David R.

Proceedings of the {$9^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1998 (pp. 490--499)

ps

Click for abstract:
We present better random sampling algorithms for maximum flows in undirected graphs. Our algorithms apply to capacitated or uncapacitated graphs, and find a maximum flow of value v in ~ O( p mnv) time. This improves on a previous bound of ~ O(m 2=3 n 1=3 v) given by the author recently, which in turn improved on the O(mv) time bound for a typical augmenting path algorithm. In uncapacitated graphs without parallel edges, the bound is no worse than ~ O(n 5=2 ). We give another algorithm that finds a (1 \Gamma ffl) times maximum flow in time ~ O(m p n=ffl), regardless of v.
Finding Maximum Flows in Simple Undirected Graphs Seems Faster than Bipartite Matching

Karger, David R. and Levine, Matthew

Proceedings of the {$29^{th}$} {ACM} Symposium on Theory of Computing , May~23--26 1998 (pp. 69--78)

ps

Click for abstract:
Considear nr r-vertex, m-edge, undirected graph with maximum llow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n@) time per path. This lets us improve the time bound of the classic augmenting path algorithm to O(m + nvsi2) on simple graphs. The addition of a blocking flow subroutine gives a simple, deterministic O(nm2/3v1/6)-time algorithm, We also use our technique to improve known randomized algorithms, giving @rtr+nv5/4)-time and d(m+-nt?~gv)-time algorithms for capacitated undirected graphs.- For simple graphs, in which v s II, the last bound is a(n2s2), improving on the best previous bound of O(n2*5), which is also the best known time bound for bipartite matching.
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP

Arora, Sanjeev, Grigni, Michelangelo, Karger, David, Klein, Philip, and Woloszyn, Andrzej

Proceedings of the {$9^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1998 (pp. 33--41)

ps.gz

Click for abstract:
Given a planar graph on $n$ nodes with costs (weights) on its edges, define the distance between nodes $i$ and $j$ as the length of the shortest path between $i$ and~$j$. Consider this as an instance of {\em metric\/} TSP. For any $\eps>0$, our algorithm finds a salesman tour of total cost at most $(1+\eps)$ times optimal in time $n^{O(1/\eps^2)}$. We also present a quasi-polynomial time algorithm for the Steiner version of this problem.

1997 (12)

Randomized Algorithms

Goemans, Michel X., Karger, David R., and Kleinberg, Jon

in Mauro Dell'Amico and Francesco Maffioli and Silvano Martello, editors, Annotated Bibliographies in Combinatorial Optimization , August 1997
Near-Optimal Interprocedural Branch Alignment

Young, Cliff, Johnson, David S., Karger, David R., and Smith, Michael D.

ACM SIGPLAN Conference on Programming Language Design and Implementation , June 1997 (pp. 183--193)

Click for abstract:
Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to controltransfer instructions. Prior work in branch alignment has produced useful heuristic methods. We compute lower bounds on the runtime costs frompipeline penalties and present an intraprocedural branch alignment algorithm that approaches the bound. We compare the control penalties and running times of our algorithm to an older, greedy approach and observe that both the greedy method and ourmethod are close to the lower bound on control penalties, suggesting that greedy is good enough. Surprisingly, in actual execution our method produces programs that run noticeably faster than the greedy method. We also report results from training andtesting on different data sets, validating that our results can be achieved in real-world usage. Training and testing on different data sets slightly reduced the benefits from both branch alignment algorithms, but not enough to change the ranking of algorithms, and not enough to completely erase the benefits from branch alignment
Improved approximation for graph coloring

Blum, Avrim and Karger, David R.

Information Processing Letters 61 (1) , January 1997 (pp. 49--53)

ps

Click for abstract:
We show how the results of Karger, Motwani, and Sudan and Blum can be combined in a natural manner to yield an $O(n^{3/14})$ coloring of any n node 3-colorable graph. This improves on the previous best bound of $O(n^{1/4})$ colors.
Derandomization Through Approximation: An {${\cal NC}$} Algorithm for Minimum Cuts

Karger, David R. and Motwani, Rajeev

SIAM Journal on Computing 26 (1) , January 1997 (pp. 255--272) A preliminary version appeared in Proceedings of the {$25^{th}$} {ACM} Symposium on Theory of Computing

ps

Click for abstract:
We show that the minimum cut and multi-cut problems in weighted undirected graphs can be solved in JVC. We do so by giving three separate and independently interesting results. The first is an m2/n processor JVC algorithm for a (2 + c)-approximation to the minimum cut. The second is a randomized reduction of the minimum cut problem to the problem of obtaining a (2+ e)-approximation to the minimum cut. This reduction involves a natural combinatorial Safe Sets Problem that can be solved easily in %?JVC. Our third result is a derandomization of this 7?JVC solution that requires a novel combination of two widely used tools: pairwise independence and random walks on expanders. We believe that the safe sets approach will prove useful in other derandomization problems.
On Approximating the Longest Path in a Graph

Karger, David R., Ramkumar, G. D. S., and Motwani, Rajeev

Algorithmica 18 (1) , May 1997 (pp. 82--98) A preliminary version appeared in the 1993 Workshop on Algorithms and Data Structures

ps

Click for abstract:
We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any e<1, the problem of finding a path of lengthn-n e in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant d>0, finding an approximation of ration d is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of $$2^{O(\log ^{1 - \varepsilon } n)} $$ , for any e>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs.
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs

Karger, David R.

Proceedings of the {$29^{th}$} {ACM} Symposium on Theory of Computing , May 1997 (pp. 240--249)

ps

Click for abstract:
We present new algorithms, based on random sampling, that find maximum flows in undirected incapacitated graphs. Our algorithms dominate augmenting paths over all parameter values (number of vertices and edges and flow value). They also dominate blocking flows over a large range of parameter values. Furthermore, they achieve time bounds on graphs with parallel (equivalently, capacitated) edges that previously could only be achieved on graphs without them. The key contribution of this paper is to demonstrate that such an improvement is possible. This shows that augmenting paths and blocking flows are non-optimal, and reopens the question of how fast we can find a maximum flow. We improve known time bounds by only a small (but polynomial) factor, and the complicated nature of our algorithms suggests they will not be practical. A new idea of our algorithm is to find flow by diminishing cuts instead of augmenting paths. Rather than finding a way to push flow from the source to the sink, we identify and delete edges that are not needed in a maximum flow. When no more edges can be deleted, we know that every remaining edge must be saturated to give a maximum flow.
Experimental Study of Minimum Cut Algorithms

Chekuri, Chandra C., Goldberg, Andrew V., Karger, David R., Levine, Matthew S., and Stein, Cliff

Proceedings of the {$8^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1997 (pp. 324--333)

Click for abstract:
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve the worst-case time bounds for the problem. In this paper, we conduct experimental evaluation the relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve the practical performance of the algorithms. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of the practical performance of minimum cut algorithms and produces very efficient codes for the problem.
Implementing a Fully Polynomial Time Approximation Scheme for All Terminal Network Reliability

Karger, David R. and Tai, Ray P.

Proceedings of the {$8^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1997 (pp. 334--343)

ps ps.gz

Click for abstract:
The classic all-terminal network reliability problem posits a graph, each of whose edges fails (disappears) independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. The practical applications of this question to communication networks are obvious, and the problem has therefore been the subject of a great deal of study. Since it is tjp-complete, and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. A comprehensive survey can be found in [Co187]. The first author recently presented an algorithm for approximating the probability of network disconnection under random edge failures. In this paper, we report on our experience implementing this algorithm. Our implementation shows that the algorithm is practical on networks of moderate size, and indeed works better than the theoretical bounds predict. Part of this improvement arises from heuristic modifications to the theoretical algorithm, while another part suggests that the theoretical running time analysis of the algorithm might not be tight. Based on our observation of the implementation, we were able to devise analytic explanations of at least some of the improved performance. As one example, we formally prove the accuracy of a simple heuristic approximation for the reliability. We also discuss other questions raised by the implementation which might be susceptible to analysis.
{(De)randomized} Construction of Small Sample Spaces in~{$\mathcal{NC}$}

Karger, David R. and Koller, Daphne

Journal of Computer and System Sciences 55 (3) , December 1997 (pp. 402--413) Special issue of selected papers from Proceedings of the {$35^{th}$} Annual Symposium on the Foundations of Computer Science

ps

Click for abstract:
Koller and Megiddo introduced the paradigm of constructing compact distributions that satisfy a given set of constraints and showed how it can be used to efficiently derandomize certain types of algorithms. In this paper, we significantly extend their results in two ways. First, we show how their approach can be applied to deal with more generalexpectation constraints. More importantly, we provide the firstparallel(NC) algorithm for constructing a compact distribution that satisfies the constraints up to a smallrelativeerror. This algorithm deals with constraints over any event that can be verified by finite automata, including allindependence constraintsas well as constraints over events relating to the parity or sum of a certain set of variables. Our construction relies on a new and independently interesting parallel algorithm for converting a solution to a linear system into an almost basic approximate solution to the same system. We use these techniques in the first NC derandomization of an algorithm for constructing large independent sets ind-uniform hypergraphs forarbitrary d. We also show how the linear programming perspective suggests new proof techniques which might be useful in general probabilistic analysis.
Job Scheduling in Rings

Fizzano, Perry, Karger, David R., Stein, Cliff, and Wein, Joel

Journal of Parallel and Distributed Computing 45 (2) , September 1997 (pp. 122--133) A preliminary version appeared in Proceedings of the {$6^{th}$} Annual {ACM}-{SIAM} Symposium on Parallel Algorithms and Architectures

Click for abstract:
We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many 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 algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.
Consistent Hashing and Random Trees: Distributed Caching protocols for Relieving Hot Spots on the World Wide Web

Karger, David R., Lehman, Eric, Leighton, Tom, Levine, Matthew, Lewin, Daniel, and Panigrahy, Rina

Proceedings of the {$29^{th}$} {ACM} Symposium on Theory of Computing , May 1997 (pp. 654--663)

ps

Click for abstract:
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, where delays caused by hot spots can be severe, and where it is not feasible for every server to have complete information about the current state of the entire network. The protocols are easy to implement using existing network protocols such as TCP/IP, and require very little overhead. The protocols work with local control, make efficient use of existing resources, and scale gracefully as the network grows. Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes. Through the development of good consistent hash functions, we are able to develop caching protocols which do not require users to have a current or even consistent view of the network. We believe that consistent hash functions may eventually prove to be useful in other applications such as distributed name servers and/or quorum systems.
Haystack: Per-User Information Environments.

Karger, David and Stein, Lynn

Manuscript , 1997

1996 (4)

A New Approach to the Minimum Cut Problem

Karger, David R. and Stein, Clifford

Journal of the ACM 43 (4) , July 1996 (pp. 601--640) Preliminary portions appeared in SODA 1992 and STOC 1993

ps doi
Minimum Cuts in Near-Linear Time

Karger, David R.

Proceedings of the {$28^{th}$} {ACM} Symposium on Theory of Computing , May 1996 (pp. 56--63) Journal version appears in Journal of the ACM 47(1)

ps

Click for 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.
A Better Algorithm for an Ancient Scheduling Problem

Karger, David R., Phillips, Steven, and Torng, Eric

Journal of Algorithms 20 , March 1996 (pp. 400--430) A preliminary version appeared in Proceedings of the {$5^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms

ps

Click for abstract:
One of the oldest and simplest variants of multiprocessor scheduling is the on-line scheduling problem studied by Graham in 1966. In this problem, the jobs arrive on-line and must be scheduled non-preemptively on m identical machines so as to minimize the makespan. The size of a job is known on arrival. Graham proved that the List Processing Algorithm which assigns each job to the currently least loaded machine has competitive ratio (2 - l/m). Recently algorithms with smaller competitive ratios than List Processing have been discovered, culminating in Bartal, Fiat, Karloff, and Vohra?s construction of an algorithm with competitive ratio bounded away from 2. Their algorithm has a competitive ratio of at most (2 - l/70) w 1.986 for all m; hence for m > 70, their algorithm is provably better than List Processing. We present a more natural algorithm that outperforms List Processing for any m 2 6 and has a competitive ratio of at most 1.945 for all m, which is significantly closer to the best known lower bound of 1.837 for the problem. We show that our analysis of the algorithm is almost tight by presenting a lower bound of 1.9378 on the algorithm?s competitive ratio for large m.
Approximate $s$--$t$ Min-Cuts in {$\Olog(n^2)$} Time

Bencz{\'u}r, Andr{\'a}s A. and Karger, David R.

Proceedings of the {$28^{th}$} {ACM} Symposium on Theory of Computing , May 1996 (pp. 47--55)

ps

1995 (6)

Polynomial Time Approximation Schemes for Dense Instances of {$\NP$}-Hard Problems

Arora, Sanjeev, Karger, David R., and Karpinski, Marek

Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing , May 1995 (pp. 284--293) Journal version appears in Journal of Computer and System Sciences

ps
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees

Karger, David R., Klein, Philip N., and Tarjan, Robert E.

Journal of the ACM 42 (2) , March 1995 (pp. 321--328)

download ps

Click for 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.
Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows

Karger, David R. and Plotkin, Serge

Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing , May 1995 (pp. 18--25)

ps

Click for abstract:
Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large class of such ?cost-added? problems?even if more than one cost is added. One of the main applications of this method is a new deterministic algorithm for approximately solving the minimumcost multicommodity flow problem. Our algorithm finds a (1 + e) approximation to the minimum cost flow in 0(e-3kmn) time, where k is the number of commodities, m is the number of edges, and n is the number vertices in the input problem. This improves the previous best deterministic bounds of O(e-4kmn2 ) [9] and 6(e-2k2m2) [15] by f~ctors of n/6 and ekm/n respectively. In fact, it even dominates the best randomized bound of 0(e-2km2) [15]. The algorithm presented in this paper efficiently solves several other interesting generalizations of rein-cost flow problems, such as one in which each commodity can have its own distinct shipping cost per edge, or one in which there is more than one cost measure on the flows and all costs must be kept small simultaneously. Our approach is based on an extension of the approximate packing techniques in [15] and a generalization of the round-robin approach of [16] to multicommodity flow without costs.
A Randomized Fully Polynomial Approximation Scheme for the All Terminal Network Reliability Problem

Karger, David R.

Proceedings of the {$27^{th}$} {ACM} Symposium on Theory of Computing , May 1995 (pp. 11--17) Journal version appears in SIAM Journal on Computing 29(2)

ps

Click for abstract:
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is $\SP$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described.
Scatter/Gather as a Tool for Navigating Search Results

Hearst, Marti A., Karger, David R., and Pedersen, Jan O.

Proceedings of the AAAI Fall Symposium on Knowledge Navigation , 1995

ps

Click for abstract:
An important information access problem arises when the user is confronted with a very large number of documents that have been retrieved in response to a query. In this paper we explore the use of a technique, called Scatter/Gather, for the navigation of large collections of retrieved documents. Scatter/Gather clusters the documents into semantically coherent groups on-the-fly and presents descriptive summaries of the groups to the user. These groups can be used in several ways: to indentify useful subsets of documents to be perused with other tools, to eliminate subsets whose contents appear nonrelevant, or to select promising document subsets for reclustering into more refined groups. This paper describes the Scatter/Gather algorithm and illustrates its application to retrieval results via two examples.
Prim-{D}ijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design

Alpert, C. J., Hu, T. C., Huang, J. H., Kahng, A. B., and Karger, David

IEEE Transactions on Computer Aided Design 14 (7) , July 1995 (pp. 890--895)

Click for abstract:
Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimal algorithms due to Prim and Dijkstra. Previous "shallow-light" techniques [2, 3, 8, 13] are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Detailed timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing.

1994 (7)

Using Randomized Sparsification to Approximate Minimum Cuts

Karger, David R.

Proceedings of the {$5^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1994 (pp. 424--432)

ps ps.gz

Click for abstract:
We develop new parallel and dynamic algorithms for approximating minimum cuts in weighted, undirected graphs. Our approach is to combine new algorithms for sparse unweighted graphs with a reduction for dense weighted graphs called {\em randomized sparsification}. Randomized sparsification yields a sparse unweighted graph that closely approximates the minimum cut structure of the original graph. In~\cite{Karger:Skeleton}, this techniques was used in sequential algorithms for approximating the minimum cut. In this paper we devise parallel and dynamic approximation algorithms. We show that a cut within a multiplicative factor of $\alpha$ of the minimum can be found in $\RNC$ using $m+n^{2/\alpha}$ processors. Using similar techniques, we give a {\em dynamic approximation algorithm} for a graph undergoing a series of edge insertions and deletions. At a cost of $\Olog(n/\epsilon^2)$ time per insertion or deletion, the algorithm will maintain a cut with value at most $(1+\epsilon)$ times the minimum. We also consider a functional inverse of randomized sparsification, and use it to develop a different dynamic algorithm that approximates the value of the minimum cut more quickly than the previous algorithm, but does not actually exhibit a cut of small value. An $O(\sqrt{1+2/\epsilon})$-approximation to the minimum cut value is maintained at a cost of $\Olog(n^{\epsilon+1/2})$ time per insertion or deletion. If only insertions are allowed, the approximation can be maintained at a cost of $\Olog(n^{\epsilon})$ time per insertion.
Approximate Graph Coloring by Semidefinite Programming

Karger, David R., Motwani, Rajeev, and Sudan, Madhu

Proceedings of the {$35^{th}$} Annual Symposium on the Foundations of Computer Science , November 1994 (pp. 2--13) Journal version appears in Journal of the ACM 45(2)

Click for abstract:
We consider the problem of coloring 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(n1/4 log1/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 k-colorable graphs to obtain a coloring using min{O(&Dgr;1-2/k log1/2 &Dgr; log n), O(n1-3/(k+1) log1/2 n)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lov?sz &thgr;-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 &thgr;-function.
A Better Algorithm for an Ancient Scheduling Problem

Karger, David R., Phillips, Steven, and Torng, Eric

Proceedings of the {$5^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1994 (pp. 132--140) Journal version appears in Journal of Algorithms 20

ps

Click for abstract:
One of the oldest and simplest variants of multiprocessor scheduling is the on-line scheduling problem studied by Graham in 1966. In this problem, the jobs arrive on-line and must be scheduled non-preemptively on m identical machines so as to minimize the makespan. The size of a job is known on arrival. Graham proved that the List Processing Algorithm which assigns each job to the currently least loaded machine has competitive ratio (2 - l/m). Recently algorithms with smaller competitive ratios than List Processing have been discovered, culminating in Bartal, Fiat, Karloff, and Vohra?s construction of an algorithm with competitive ratio bounded away from 2. Their algorithm has a competitive ratio of at most (2 - l/70) w 1.986 for all m; hence for m > 70, their algorithm is provably better than List Processing. We present a more natural algorithm that outperforms List Processing for any m 2 6 and has a competitive ratio of at most 1.945 for all m, which is significantly closer to the best known lower bound of 1.837 for the problem. We show that our analysis of the algorithm is almost tight by presenting a lower bound of 1.9378 on the algorithm?s competitive ratio for large m.
(De)Randomized Construction of Small Sample Spaces in {$\NC$}

Karger, David R. and Koller, Daphne

Proceedings of the {$35^{th}$} Annual Symposium on the Foundations of Computer Science , November 1994 (pp. 252--263) Journal version appears in Journal of Computer and System Sciences 55

ps

Click for abstract:
Koller and Megiddo introduced the paradigm of constructing compact distributions that satisfy a given set of constraints and showed how it can be used to efficiently derandomize certain types of algorithms. In this paper, we significantly extend their results in two ways. First, we show how their approach can be applied to deal with more general expectation constraints.More importantly, we provide the first parallel (𝒩𝒞) algorithmfor constructing a compact distribution that satisfies the constraintsup to a small relative error. This algorithm deals with constraintsover any event that can be verified by finite automata, includingall independence constraints as well as constraints over eventsrelating to the parity or sum of a certain set of variables.Our construction relies on a new and independently interestingparallel algorithm for converting a solution to a linear systeminto an almost basic approximate solution to the same system.We use these techniques in the first 𝒩𝒞 derandomization of analgorithm for constructing large independent sets in d-uniformhypergraphs for arbitrary d. We also show how the linear programmingperspective suggests new proof techniques which might be usefulin general probabilistic analysis.
Job Scheduling in Rings

Fizzano, Perry, Karger, David R., Stein, Cliff, and Wein, Joel

Proceedings of the {$6^{th}$} Annual {ACM}-{SIAM} Symposium on Parallel Algorithms and Architectures , June 1994 (pp. 210--219) Journal version appears in Journal of Parallel and Distributed Computing 45(2)

ps

Click for abstract:
We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many 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 algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.
Random Sampling in Cut, Flow, and Network Design Problems

Karger, David R.

Proceedings of the {$26^{th}$} {ACM} Symposium on Theory of Computing , May 1994 (pp. 648--657) Journal version appears in Mathematics of Operation Research 24(2), 1999

ps

Click for abstract:
We explore random sampling as a tool for solving undirected graph problems. We show that the sparse graph's or skeleton, which arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph. This makes sampling effective for problems involving cuts in graphs. We apply these tools in fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding cuts and flows in an unweighted, undirected graph. We also give weighted-graph versions of these algorithms which use a form of scaling to achieve a sublinear dependence on the maximum edge weight. Our methods also reduce the work done by some parallel cut algorithms. Our sampling theorems also yield faster algorithms for several other cut based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our sampling theorems apply even when the sampling probabilities are different for different edges. Using this fact, we show how to use randomized rounding in (1+0(1))-approximation algorithm for the NP-complete minimum $k$-connected subgraph problem when $k > log n$; the best previous approximation factor was $\log k$. Our techniques generalize to many other survivable network design problems.
Random Sampling in Graph Optimization Problems

Karger, David R.

, 1994 Contact at {\tt karger@lcs.mit.edu.} Available from {\tt http://theory.lcs.mit.edu/\~{}karger} Winner, ACM Doctoral Dissertation Award, 1995. To be published by Springer Verlag

ps

Click for 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 investiga tor's work, both in gathering and in analyzing the data. We apply the concept of a representative sample to combinatorial optimization. Our general technique is to generate small random representative subproblems and solve them in lieu of the original ones, producing approximately correct answers which may then be refined to correct ones at little additional cost. Our focus is optimization problems on undirected graphs. Highlights of our results include \begin{itemize} \item The first (randomized) linear time minimum spanning tree algorithm \item A (randomized) minimum cut algorithm with running time roughly $O(n^2)$ as compared to previous roughly $O(n^3)$ time bounds, as well as the first algorithm for finding all approximately minimal cuts and multiway cuts \item An efficient parallelization of the minimum cut algorithm, providing the first parallel (RNC) algorithm for minimum cuts \item The first proof that minimum cuts can be found deterministically in parallel (NC) \item Reliability theorems tightly bounding the connectivities and bandwidths in networks with random edge failures, and a fully polynomial time approximation scheme for estimating all-terminal reliability---the probability a particular graph remains connected under edge failures \item A linear time algorithm for approximating minimum cuts to within $1+\epsilon$ and a linear processor parallel algorithm for $1+\epsilon$ approximation, and fast algorithms for approximat ing $s$-$t$ minimum cuts and maximum Flows

1993 (8)

Derandomization Through Approximation: An {${\cal NC}$} Algorithm for Minimum Cuts

Karger, David R. and Motwani, Rajeev

Proceedings of the {$25^{th}$} {ACM} Symposium on Theory of Computing , May 1993 (pp. 497--506) Journal version appears in SIAM Journal on Computing 26(1)

ps

Click for abstract:
We show that the minimum cut and multi-cut problems in weighted undirected graphs can be solved in JVC. We do so by giving three separate and independently interesting results. The first is an m2/n processor JVC algorithm for a (2 + c)-approximation to the minimum cut. The second is a randomized reduction of the minimum cut problem to the problem of obtaining a (2+ e)-approximation to the minimum cut. This reduction involves a natural combinatorial Safe Sets Problem that can be solved easily in %?JVC. Our third result is a derandomization of this 7?JVC solution that requires a novel combination of two widely used tools: pairwise independence and random walks on expanders. We believe that the safe sets approach will prove useful in other derandomization problems.
On Approximating the Longest Path in a Graph

Karger, David R., Ramkumar, G. D. S., and Motwani, Rajeev

WADS93: Algorithms and Data Structures : Third Workshop (709) , August 1993 (pp. 421--430) Journal version appears in Algorithmica 18(1)

Click for abstract:
We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any e<1, the problem of finding a path of lengthn-n e in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant d>0, finding an approximation of ration d is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of $$2^{O(\log ^{1 - \varepsilon } n)} $$ , for any e>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs.
An {$\Olog(n^2)$} Algorithm for Minimum Cuts

Karger, David R. and Stein, Clifford

Proceedings of the {$25^{th}$} {ACM} Symposium on Theory of Computing , May 1993 (pp. 757-765) Journal version appears in Journal of the ACM 43(4)

ps

Click for 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(n2log3n) 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 RNC with n2 processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of &agr; of the minimum cut's in expected O?(n2&agr;) time, or in RNC with n2&agr; processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected O?(n2(r-1)) time, or in RNC with n2(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.
Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees

Karger, David R.

Proceedings of the {$34^{th}$} Annual Symposium on the Foundations of Computer Science , November 1993 (pp. 84--93) Journal version appears in Mathematical Programming B 82(1--2)

ps

Click for abstract:
Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: Finding an optimum matroid basis and packing disjoint matroid bases. Applications of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by a greedy algorithm that grows an independent set into an the optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a given fixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems.
Global Min-cuts in {$\RNC$} and Other Ramifications of a Simple Mincut Algorithm

Karger, David R.

Proceedings of the {$4^{th}$} Annual {ACM}-{SIAM} Symposium on Discrete Algorithms , January 1993 (pp. 21--30) Journal version appears in Journal of the ACM43(4)

ps

Click for abstract:
This paper presents a new algorithm for finding global min-cuts in weighted, undirected graphs. One of the strengths of the algorithm is its extreme simplicity. This randomized algorithm can be implemented as a strongly polynomial sequential algorithm with running time 6(mn2), even if space is restricted to O(n), or can be parallelized as an Zn/C algorithm which runs in time O(log2 n) on a CRCW PRAM with mn2 log n processors. In addition to yielding the best known processor bounds on unweighted graphs, this algorithm provides the first proof that the min-cut problem for weighted undirected graphs is in 7ZAfC. The algorithm does more than find a single mm-cut; it finds all of them. The algorithm also yields numerous results on network reliability, enumeration of cuts, multi-way cuts, and approximate mm-cuts. 1
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

Karger, David R., Koller, Daphne, and Phillips, Steven J.

SIAM Journal on Computing 22 (6) , December 1993 (pp. 1199--1217) A preliminary version appeared in Proceedings of the {$32^{nd}$} Annual Symposium on the Foundations of Computer Science

ps

Click for abstract:
The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm?the Hidden-Paths Algorithm?that finds these paths in time $O(m^ * n + n^2 \log n)$, where $m^ * $ is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra's algorithm. It is argued that $m^ * $ is likely to be small in practice since $m^ * = O(n\log n)$ with high probability for many probability distributions on edge weights. An $\Omega (mn)$ lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms of E. W. Dijkstra [Numer. Math., 1 (1959), pp. 269?271] and R. W. Floyd [Comm. ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more general setting.
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

Karger, David R., Koller, Daphne, and Phillips, Steven J.

SIAM Journal on Computing 22 (6) , December 1993 (pp. 1199--1217) A preliminary version appeared in Proceedings of the {$32^{nd}$} Annual Symposium on the Foundations of Computer Science

ps

Click for abstract:
The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm?the Hidden-Paths Algorithm?that finds these paths in time $O(m^ * n + n^2 \log n)$, where $m^ * $ is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra's algorithm. It is argued that $m^ * $ is likely to be small in practice since $m^ * = O(n\log n)$ with high probability for many probability distributions on edge weights. An $\Omega (mn)$ lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms of E. W. Dijkstra [Numer. Math., 1 (1959), pp. 269?271] and R. W. Floyd [Comm. ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more general setting.
Constant Interaction-Time Scatter/Gather Browsing of Very Large Document Collections

Cutting, Douglas, Karger, David R., and Pedersen, Jan

Proceedings of the {$16^{th}$} Annual International {ACM} {SIGIR} Conference on Research and Development in Information Retrieval , July 1993 (pp. 126--134) Pittsburgh, PA

ps

Click for 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.

1992 (3)

Fast Connected Components Algorithms for the {EREW} {PRAM}

Karger, David R., Nisan, Noam, and Parnas, Michal

Proceedings of the {$4^{th}$} Annual {ACM}-{SIAM} Symposium on Parallel Algorithms and Architectures , June 1992 (pp. 562-572) Journal version appears in SIAM Journal on Computing 28(3)

ps

Click for abstract:
We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using $(m+n^{1+\epsilon})/\log n$ EREW processors (for any fixed $\epsilon>0$). A variant uses (m+n)/log n processors and runs in O(log n log log n) time. A deterministic version of the algorithm runs in $O(\log^{1.5}n)$ time using m+n EREW processors.
Approximating, Verifying, and Constructing Minimum Spanning Forests

Karger, David R.

Manuscript , 1992 Manuscript.
Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections

Cutting, Douglas, Karger, David R., Pedersen, Jan, and Tukey, John W.

Proceedings of the {$15^{th}$} Annual International {ACM} {SIGIR} Conference on Research and Development in Information Retrieval , 1992 (pp. 318-329)

ps doi

Click for 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.

1991 (1)

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

Karger, David R., Koller, Daphne, and Phillips, Steven J.

Proceedings of the {$32^{nd}$} Annual Symposium on the Foundations of Computer Science , October 1991 (pp. 560--568) Journal version appears in SIAM Journal on Computing 22(6)

ps

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