Po-An Chen, David Kempe: Altruism, Selfishness, and Spite in Traffic Routing. To appear in Proceedings of EC 2008, Chicago, IL. [Formats: PDF]
We study traffic routing under the assumption that the users are "partially altruistic", meaning that while they prefer to choose faster routes for themselves, they trade off their own gain with the congestion they impose on others. We show that even a small amount of (uniform) altruism reduces the price of anarchy to a constant. In parallel link networks, even a small average level of altruism has the same effect.
Abhimanyu Das, David Kempe: Algorithms for Subset Selection in Linear Regression. To appear in Proceedings of STOC 2008, Victoria, BC. [Formats: PDF]
We study the problem of selecting a subset of random variables to sample to minimize the prediction error of the resulting linear regression, given all covariances of pairs of random variables. Using perturbation analysis, dynamic programming, and other optimization techniques, we provide exact and approximation algorithms under restrictions on the structure of the covariance matrix. We also give sufficient conditions for the frequently used Forward Regression to produce near-optimal results or a constant-factor approximation.
Abhimanyu Das, David Kempe: Sensor Selection for Minimizing Worst-Case Prediction Error. To appear in Proceedings of IPSN 2008, St. Louis, MO. [Formats: PDF]
We study the problem of selecting a set of sensors to sample so as to minimize the worst-case prediction error of an aggregation function, when the actual sensor readings are chosen by an adversary subject to a hard metric constraint. We prove that the selection problem for estimating the average is equivalent to k-median, and for the maximum/minimum to k-center. We generalize these results to other aggregation functions, and also validate our algorithms on real-world sensor measurements.
Bruce Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani: Fast Asynchronous Byzantine Agreement and Leader Election with Full Information. In Proceedings of SODA 2008, San Francisco, CA. [Formats: PDF]
We give the first subexponential time protocols for Byzantine Agreement and Leader Election in the asynchronous full-information model. This resolves a long-standing open problem. In fact, our protocols take poly-logarithmic time, succeeding with high (Agreement) or constant (Election) probability. The key technique is a novel protocol for asynchronous universe reduction, based on an extension of Feige's protocol.
Atsushi Iwasaki, David Kempe, Yasumasa Saito, Mahyar Salek, Makoto Yokoo: False-name-proof mechanisms for hiring a team. In Proceedings of WINE 2007, San Diego, CA. [Formats: PDF]
We study false-name proof auctions in which an auctioneer is trying to hire a team of elements owned by individually paid agents. The goal is to design incentive-compatible mechanisms which will make agents reveal both ownership of elements and true costs, while minimizing total payments. We formally present two natural models. For one, we give an O(n2n) competitive mechanisms, and prove a lower bound of Ω(2n). For the second, we present a mechanism with a reserve price, which does not always purchase a solution.
Shishir Bharathi, David Kempe, Mahyar Salek: Competitive Influence Maximization in Social Networks. In Proceedings of WINE 2007, San Diego, CA. [Formats: PDF]
We study viral marketing in a scenario of multiple competing companies. We give a 1-1/e approximation for the last mover, prove a price of anarchy of 2, give first-mover algorithms for some very restricted graph structure, and present an FPTAS for the one-company version on bidirected trees.
Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg: A Knapsack Secretary Problem with Applications. In Proceedings of APPROX 2007, Princeton, NJ. [Formats: PDF]
We study a Knapsack Secretary problem, where items with weights and values (chosen adversarially) arrive in a random order, and an algorithm should select a set of maximum value subject to a hard weight constraint, in an online fashion. We give a randomized constant-factor online algorithm for this problem, and improve the constant to 1/e if the items have uniform weights.
Chayant Tantipathananandh, Tanya Berger-Wolf, David Kempe: A Framework for Community Identification in Dynamic Social Networks. In Proceedings of KDD 2007, San Jose, CA. [Formats: PDF]
We propose an optimization-based framework for identifying communities in a social network whose membership and connections change over time. Our framework is based on natural observations that individuals do not change group memberships frequently, and do not alternate between many groups. We propose optimal algorithms and heuristics, and evaluate them on several real-world data sets.
David Kempe, Adam Meyerson, Nainesh Solanki, Ramnath Chellappa: Pricing Partially Compatible Products. In Proceedings of ECOM 2007, San Diego, CA. [Formats: PDF]
We study the problem of pricing individual components of a system when components from rival companies may vary in their compatibility. Such incompatibilities can be exploited by charging higher prices for inferior products, due to higher compatibility. We give a polynomial-time algorithm for the best-response pricing problem, and hardness results and approximation algorithms for the problems of optimal product improvement and compatibility alterations.
Omid Madani, Wiley Greiner, David Kempe, Mohammad Salavatipour: Recall Systems: Efficient Learning and Use of Category Indices. In Proceedings of AISTATS 2007, San Juan, Puerto Rico. [Formats: PDF]
We propose "Recall Systems" as an efficient preprocessing step for learning category indices. The idea is to use simple feature-based classifiers to reduce the number of remaining candidates to a managable set before applying traditional classifiers. We prove hardness results for finding optimal categories, give heuristics, and evaluate then on large data sets in practice.
Michael Collins, David Kempe, Jared Saia, Maxwell Young: Nonnegative Integral Subset Representation of Integer Sets. In Information Processing Letters, Vol 101/3, 02/2007, pp. 129-133. [Formats: PDF]
Motivated by applications in radiation therapy, we study the problem of representing a set of integers by a "smaller" set. By this, we mean that each element of the given set is the sum of a subset of elements from the representing set. We prove that finding the best representing set is NP-complete, investigate lower bounds, and evaluate heuristics experimentally.
Fang Bian, David Kempe, Ramesh Govindan: Utility-based Sensor Selection. In Proceedings of IPSN 2006, San Antonio, TX. [Formats: PDF]
Sensor network applications face a tradeoff between the amount of data that can be retrieved and the lifetime of the network. Many recent papers have addressed this tradeoff with ad hoc approaches for maximizing lifetime. Here, we argue that a more formal approach is useful: to maximize the total utility that the network can generate with its measurements. The utility function is user-specified and application-sepecific. For several classes of natural utility functions, we give hardness results, polynomial-time algorithms, or approximation algorithms.
Anna Karlin, David Kempe, Tami Tamir: Beyond VCG: Frugality of Truthful Mechanisms. In Proceedings of FOCS 2005, Pittsburgh, PA. [Formats: Postscript or PDF]
We study the problem of hiring a team of agents. Each agent submits a bid, and a feasible set of agents is to be hired and paid. We propose a new and intuitive measure of the frugality of a mechanism in this setting, and give competitive mechanisms for path auctions and a class of set systems termed k-out-of-r systems.
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina: Unbalanced Graph Cuts. In Proceedings of ESA 2005, Mallorca, Spain. [Formats: Postscript or PDF]
We propose the study of unbalanced graph cuts: cuts with a given capacity bound on edges, leaving as few nodes on the s-side of the cut as possible. The problem has applications in the containment of disasters and epidemics, but also in finding dense communities in social networks or the web graph. We present a 2/2 bicriteria approximation, and a polynomial time algorithm for graphs of bounded treewidth.
Xiaoming Zheng, Sonal Jain, Sven Koenig, David Kempe: Multi-Robot Forest Coverage. In Proceedings of IROS 2005, Edmonton, Canada. [Formats: Postscript or PDF]
We study the problem of visiting all nodes of a graph with multiple robots. After proving several versions of the problem NP-hard, we experimentally evaluate an approximation algorithm of Even et al., and show that it significantly outperforms techniques currently used in robotics.
David Kempe, Jon Kleinberg, Éva Tardos: Influential Nodes in a Diffusion Model for Social Networks. In Proceedings of ICALP 2005, Lisboa, Portugal. [Formats: Postscript or PDF]
An extension of the paper "Maximizing the Spread of Influence in a Social Network", this paper studies a more general diffusion model termed "Decreasing Cascade Model." We prove that the greedy algorithm is a (1-1/e) approximation in that model, using more involved techniques than in the previous paper.
Michail Lagoudakis, Vangelis Markakis, David Kempe, Pinar Keskinocak, Sven Koenig, Anton Kleywegt, Craig Tovey, Adam Meyerson, Sonal Jain: Auction-Based Multi-Robot Routing. In Proceedings of Robotics 2005, Boston, MA. [Formats: Postscript or PDF]
We study simple bidding-based heuristics for assigning targets to multiple robots, leading to greedy algorithms that can be easily implemented in a decentralized way. We prove upper and lower bounds on the performance of these heuristics for three objectives: total energy, completion time, and average latency.
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cris Moore.
On the Bias of Traceroute Sampling, or: Power-law Degree Distributions
in Regular Graphs.
In Proceedings of STOC 2005, Baltimore, MD.
[Formats: Postscript or PDF]
We study the degree distribution of BFS trees in random graphs, and give a characterization of the observed degrees as a function of the actual ones. In particular, we observe a power law with exponent -1 in regular random graphs. As BFS trees are a good model for single-source all-destinations traceroutes, this analytically characterizes the bias of traceroute sampling, observed empirically by Lakhina et al.
We study the problem of pricing items for profit maximization in a combinatorial setting when the desired bundles and price caps of all customers are known. In particular, we study the special case of single-minded bidders, who are only interested in one bundle if they can afford it. Even this case is APX-hard, so we study approximation algorithms as well as further special cases, including customers interested in paths to a tree's root.
David Kempe, Frank McSherry:
A Decentralized Algorithm for Spectral Analaysis.
In Journal of Computer and System Sciences, Vol. 74/1, 02/2008, pp.70-83.
A preliminary version appeard in
Proceedings of STOC 2004, Chicago, IL.
[Full version in Postscript or PDF]
We present and analyze a simple decentralized algorithm for computing the top k eigenvectors of a symmetric matrix, when the nodes of a network know only the matrix entries corresponding to their rows. By utilizing the nodes in the network for the computation, the algorithm manages to be exponentially faster than centralized algorithms, and at the same time avoids the problem of having to collect the data.
Leonid Meyerguz, David Kempe, Jon Kleinberg, Ron Elber:
The Evolutionary Capacity of Protein Structures.
In Proceedings of RECOMB 2004, San Diego, CA.
[Formats: Postscript or PDF]
We define the evolutionary capacity of a protein sequence as the number of sequences that have lower energy in the shape of the given protein sequence. Thus, the evolutionary capacity captures how much room for improvement exists over the native sequences. We present and analyze an approximation algorithm based on random sampling.
David Kempe, Alin Dobra, Johannes Gehrke:
Computing Aggregate Information using Gossip.
In Proceedings of FOCS 2003, Boston.
[Formats: Postscript or PDF]
We present and analyze simple algorithms for decentralized protocols to compute aggregate functions, such as sums, averages, random samples, quantiles, etc. We show that when using Uniform Gossip for communication, the protocols converge to the true answer exponentially fast. We give a general framework that separates the details of the protocol from the communication mechanism, and analyze their mutual influence. In particular, we also analyze the convergence speed for flooding.
David Kempe, Jon Kleinberg, Éva Tardos:
Maximizing the Spread of Influence in a Social Network.
In Proceedings of KDD 2003, Washington DC.
Recipient of best paper award.
[Formats: Postscript or PDF]
We study the problem of how to spread an innovation in a network, such as a social network. We consider several standard models from the sociology literature, and provide a constant-factor approximation algorithm for the problem of how to spend a given marketing budget to reach as large a fraction of the network as possible in expectation.
David Kempe, Jon Kleinberg:
Protocols and Impossibility Results for Gossip-Based Communication Mechanisms.
In Proceedings of FOCS 2002, Vancouver.
[Formats: Postscript, PDF]
This paper studies how the choice of gossip distributions affects which problems can be solved efficiently with small messages in a distributed setting. In particular, it presents a simple approximation algorithm for finding a minimum spanning tree using spatial gossip (see below), and shows that using uniform gossip, neither the MST problem nor the resource location problem (see below) can be approximated fast and with small messages.
Elliot Anshelevich, David Kempe, Jon Kleinberg:
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.
Full version to appear in SIAM Journal of Computing. A preliminary version appeared
in Proceedings of STOC 2002, Montréal.
[Full version in Postscript or
PDF.]
We study the load balancing and packet routing problems in a dynamic online setting, where an adversary can insert and remove jobs or packets. We give simple proofs of stability for a natural distributed algorithm against rate-1 adversaries, for load balancing with up to 2 commodities, and packet routing with a single sink. A main contribution of the paper is a new proof technique for stability proofs.
Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe,
Pablo Moisset de Espanés, Paul Rothemund:
Combinatorial Optimization Problems in Self-Assembly.
In Proceedings of STOC 2002, Montréal.
Invited to a special issue of Journal of Computer and System Sciences
devoted to selected papers from the conference.
[Formats: Postscript, PDF].
Self-assembly is the process by which small simple objects (tiles) autonomously aggregate into larger and more difficult complexes. We study the question of designing systems of a small number of distinct tiles that assemble into a desired structure, and of choosing tile concentrations to achieve fast assembly. Among others, we show that it is NP-complete to find the smallest tile system producing uniquely a desired shape. The algorithm that proves membership in NP is of interest in its own right as a verification procedure.
David Kempe, Jon Kleinberg, Alan Demers:
Spatial Gossip and Resource Location Protocols.
Journal of the ACM, Vol. 51/6, 11/2004, pp.943-967.
A preliminary version appeared in the
Proceedings of STOC 2001, Crete, Greece.
Full version in Postscript or PDF.
This paper analyzes a class of gossip distributions termed "spatial gossip", in which the probability of communication between two nodes depends inversely polynomially on their distance. It proves that information travels distance d in time poly-logarithmic in d, with high probability. Spatial Gossip is then used to design very simple protocols for the "Resource Location Problem", in which each node is supposed to be informed the closest copy of some desirable resource.
David Kempe, Jon Kleinberg, Amit Kumar:
Connectivity and Inference Problems for Temporal Networks.
Journal of Computer and System Sciences 64 (2002).
A preliminary version appeared in the Proceedings of STOC 2000, Portland.
Full version in Postscript or PDF.
We propose the study of "temporal networks", graphs with time labels on the edges, as a combinatorial structure to capture the dynamics of information dissemination. Time-respecting paths, those with increasing time labels, correspond naturally to the flow of information. Our main result is an excluded minor theorem, showing that the number of node-disjoint time respecting s-t paths is equal to the size of a minimum s-t cutset for all time labelings, if and only if the graph does not contain a certain 5-node graph as a topological minor.
David Kempe: On the Complexity of the Reflections game.
Unpublished Manuscript.
[Formats: Postscript, PDF]
The result of a few afternoons spent playing a puzzle game on the computer. In "Reflections", a player places optical objects (such as mirrors and items to split light beams) on a grid, trying to hit a given set of light bulbs. This paper proves that solving levels of the game is an NP-complete problem.
The publications listed below stem from my undergraduate work in theorem proving and algebraic specification, which I did at the Universität Karlsruhe. They include my "Diplomarbeit" (roughly corresponding to a master's thesis).
Arno Schönegge, David Kempe:
On the weakness of conditional equations in algebraic specification (Postscript).
In Proceedings of DMTCS 1999, Auckland, New Zealand.
We prove that there are recursive, monomorphic abstract data types which can be specified with quantifier-free first-order formulas under loose semantics but not with conditional equations under initial semantics (both not allowing auxiliary functions). See below for some context.
David Kempe, Arno Schönegge:
On the power of quantifiers in first-order algebraic specification (Postscript).
In Proceedings of CSL 1998, Brno, Czech republic.
We prove that there are recursive, monomorphic abstract data types specifiable with full first-order logic, but not without quantifiers (both under loose semantics, and without allowing auxiliary functions). While the result seems intuitively obvious, it is surprisingly non-trivial to prove. As with the paper above, this is part of a larger effort (Arno Schönegge's PhD thesis) to compare expressive power of different commonly used methods of specifying abstract data types.
Diplomarbeit:
Ausdrucksmächtigkeit von
Quantoren in algebraischen Spezifikationen (Postscript).
(Expressive power of quantifiers in algebraic specification).
Thesis advisor: Arno Schönegge.
In German, 08/1998.
An extended version of the above paper, in German. The core idea is the same, but it is complemented by several related results, and gives more detail and definitions.
Martin Giese, David Kempe, Arno Schönegge:
KIV zur Verifikation von ASM-Spezifikationen
am Beispiel der DLX-Pipelining Architektur (Postscript).
(Using KIV for verifying ASM specifications: Verification of the DLX pipelining architecture).
Technical Report 16/97,
Fakultät für Informatik, Universität Karlsruhe, Germany.
In German.
A report (in German) on a case study which investigated how the KIV system could be used to verify the correctness of hardware architectures. It describes the formalization of correctness criteria (showing that the most basic version of the processor produces the same results as a pipelined one), and the techniques used in interactively proving the results.
Back to my home page