Home               Contact info

Robert Kleinberg's Publications

Click on a link to go directly to one of these topics:

Economic Aspects of Algorithms

Load balancing without regret in the billboard model
R. Kleinberg, G. Piliouras, and É Tardos.
To appear in Proceedings of the 28th Symposium on Principles of Distributed Computing (PODC 2009).
Paper is in preparation. Link coming soon.
We analyze the performnce of protocols for load balancing in distributed systems based on no-regret algorithms from online learning theory. These protocols treat load balancing as a repeated game and apply algorithms whose average performance over time is guaranteed to match or exceed the average performance of the best strategy in hindsight. Our approach captures two important aspects of distributed systems. First, in our setting of atomic load balancing, every single process can have a significant impact on the performance and behavior of the system. Furthermore, although in distributed systems participants can query the current state of the system, they cannot reliably predict the effect of their actions on it. We address this issue by considering load balancing games in the bulletin board model, where players can find out the delay on all machines, but do not have information on what their experienced delay would have been if they had selected another machine. We show that under these more realistic assumptions, if all players use the well-known multiplicative weights algorithm, then the quality of the resulting solution is exponentially better than the worst correlated equilibrium, and almost as good as that of the worst Nash equilibrium.

Selling ad campaigns: Online algorithms with cancellations
M. Babaioff, J. D. Hartline, and R. Kleinberg.
To appear in Proceedings of the 10th Annual ACM Conference on Electronic Commerce (EC 2009).
We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, the cost of such a cancellation is a fixed fraction of the price originally charged. We analyze a simple constant-competitive algorithm for selling a single item (or, more generally, a matroid basis) in this model, proving that its competitive ratio is optimal among deterministic algorithms but that the competitive ratio can be improved using randomized algorithms. We then model ad campaigns using “knapsack domains”, in which the requests differ in size as well as in value. We give a deterministic bi-criterion approximation in which both factors approach 1 as the buyback factor and the size of the maximum request approach 0.

Multiplicative updates outperform generic no-regret learning in congestion games
R. Kleinberg, G. Piliouras, and É. Tardos.
To appear in Proceedings of the 41th ACM Symposium on Theory of Computing (STOC 2009).
We study the dynamics of repeated atomic congestion games whose players update their mixed strategies using the well-known weighted majority learning algorithm. Atomic congestion games have a wide variety of equilibria often with vastly differing social costs. We show that in almost all such games, the well-known multiplicative-weights learning algorithm results in convergence to pure equilibria. In fact, the dynamics always converges to a type of mixed Nash equilibrium that we call weakly stable. Pure Nash equilibria are weakly stable, and the converse holds outside of a measure-zero set of games whose edge costs are contained in the zero-set of a nonvanishing polynomial. Our results thus show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy, or the price of total anarchy, in atomic congestion games. Our proof is based on approximating the learning process by a continuous-time differential equation, and analyzing this differential equation using tools from dynamical systems and algebraic geometry to extract a game-theoretic interpretation of its stable fixed points.

Characterizing truthful mechanisms with convex type spaces
A. Archer and R. Kleinberg.
SIGecom Exchanges 7(3), November 2008.
This article contains an annotated discussion of Archer and Kleinberg's paper Truthful germs are contagious: A local-to-global characterization of truthfulness that characterizes truthful mechanisms with convex type spaces and potentially infinite outcome spaces. Characterization theorems for truthful mechanisms, when they exist, are a boon to the mechanism designer since they allow us to reduce problems of optimal mechanism design to algorithm design problems in which the algorithm that computes the allocation function is required to satisfy additional constraints.

Online auctions and generalized secretary problems
M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg.
SIGecom Exchanges 7(2), June 2008.
This article surveys several recent papers on generalizations of the famous secretary problem and their applications to the analysis of online auctions. All of these problems involve designing online algorithms to choose a set of elements from a randomly-ordered sequence, subject to constraints on the set of elements which may be picked.
Selling banner ads: Online algorithms with buyback
M. Babaioff, J. D. Hartline, and R. Kleinberg.
Workshop on Ad Auctions 2008, Chicago, Illinois, USA.
We initiate the study of online pricing problems in markets with "buyback," i.e., markets in which prior allocation decisions can be revoked, but at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising, in which the buyback cost represents the cost of canceling an existing contract.
Truthful germs are contagious: A local-to-global characterization of truthfulness
A. Archer and R. Kleinberg.
In Proceedings of the 9th ACM Conference on Electronic Commerce (EC 2008), pp. 21-30.
We study the question of how to easily recognize whether a social choice function f from an abstract type space to a set of outcomes is truthful, i.e. implementable by a truthful mechanism. We provide a local-to-global characterization theorem for any set of outcomes (possibly infinite) and any convex space of types (possibly infinite-dimensional): f is truthful if its restriction to every sufficiently small 2-dimensional neighborhood about each point is truthful. Using our characterization theorem we give a simple alternate derivation of the Saks-Yu theorem that weak monotonicity implies truthfulness for convex type spaces and finite outcome sets. We also show that the reliance on unboundedly-large subsets is inevitable in any characterization of truthfulness with infinite outcome sets: for every integer k there are non-truthful functions whose restriction to every k-point subset of the type space is truthful.
A knapsack secretary problem with applications
M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg.
In Proceedings of the 10th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX 2007), pp. 16-28.
We consider situations in which a decision-maker with a fixed budget faces a sequence of options, each with a cost and a value, and must select a subset of them online so as to maximize the total value. Such situations arise in many contexts, e.g., hiring workers, scheduling jobs, and bidding in sponsored search auctions. This problem, often called the online knapsack problem, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a random order, which makes our problem into a generalization of the classical secretary problem. We call this the knapsack secretary problem and we present a constant-competitive algorithm for arbitrary costs and values.
Automated online mechanism design and prophet inequalities
M. Hajiaghayi, R. Kleinberg, and T. Sandholm.
In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pp. 58-65.
We develop algorithms that compute an optimal, or approximately optimal, online auction mechanism for digital goods given distributional knowledge of bid values. We first prove that when the seller does not know the market size, no constant-approximation to the optimum efficiency or revenue is achievable in the worst case. Second, we show that when the seller has distributional knowledge of the market size as well as the bid values, one can combine dynamic programming with prophet inequalities (a technique from optimal stopping theory) to design and analyze online mechanisms which are truthful (even with respect to arrival and departure times) and which approximately maximize revenue or efficiency.
Congestion games with malicious players
M. Babaioff, R. Kleinberg, and C. Papadimitriou.
In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), pp. 103-112.
We study the equilibria of nonatomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the average delay experienced by the rational players. We study the existence of pure and mixed Nash equilibria for these games, and we seek to quantify the impact of the malicious players on the equilibrium. One counterintuitive phenomenon which we demonstrate is the "windfall of malice": paradoxically, when a myopically malicious player gains control of a fraction of the flow, the new equilibrium may be more favorable for the remaining rational players than the previous equilibrium.

Algorithmic pricing via virtual valuations
S. Chawla, J. Hartline, and R. Kleinberg.
In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), pp. 243-251.
We consider the algorithmic problem of computing approximately profit-maximizing prices in a unit-demand, multi-product scenario when the consumer's valuations for the different items are independent random variables. Using a connection between this problem and the concept of virtual valuations from single-parameter Bayesian optimal mechanism design, we design a 4-approximation algorithm for this multi-parameter pricing problem.

Matroids, secretary problems, and online mechanisms
Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 434-443.
The matroid secretary problem is a generalization of the classical secretary problem. An algorithm observes the elements of a weighted matroid in random order. As each element is observed, the algorithm makes an irrevocable decision to choose it or skip it, with the constraint that the chosen elements must constitute an independent set. The objective is to maximize the combined weight of the chosen elements. This paper raises the question of whether every matroid admits a constant-competitive secretary algorithm, and solves the question for certain special classes of matroids.

Secretary problems with competing employers
Nicole Immorlica, Robert Kleinberg, and Mohammad Mahdian.
In Proceedings of the 2nd Workshop on Internet and Network Economics (WINE 2006), pp. 389-400.
In many decentralized labor markets, job candidates are offered positions at very early stages in the hiring process. We explore this phenomenon by studying the equilibria of a game based on the secretary problem with competing employers. Our results confirm the observation of early offers in labor markets: for several classes of strategies based on optimal stopping theory, as the number of employers grows, the timing of the earliest offer approaches zero.

On the competitive ratio of the random sampling auction
Uriel Feige, Abraham Flaxman, Jason Hartline, and Robert Kleinberg.
In Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), pp. 878-886.
We give a simple analysis of the competitive ratio of the random sampling auction introduced by Goldberg, Hartline, and Wright in 2001. Our analysis improves the best known bound on this auction's competitive ratio from 7600 to 15. In support of the conjecture that the random sampling auction is in fact 4-competitive, we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.

Online auctions with re-usable goods
Mohammad Hajiaghayi, Robert Kleinberg, Mohammad Mahdian, and David Parkes.
In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM-EC 2005), pages 165--174.
This paper concerns the design of mechanisms for online scheduling in which agents bid for access to a re-usable resource such as processor time or wireless network access. Agents are assumed to arrive and depart dynamically over time. We design mechanisms that are truthful in the sense that truthful revelation of arrival, departure, and value information is a dominant strategy, and that are online in the sense that they make allocation and payment decisions without knowledge of the future. We also prove some general characterization theorems and lower bounds for such mechanisms.

A multiple-choice secretary problem with applications to online auctions
Robert Kleinberg.
In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 630-631.
A sequence of n positive numbers is presented to an algorithm in random order. After seeing each number, the algorithm must decide whether to keep or reject it. Such decisions are irrevocable, and the algorithm may only keep k numbers altogether. When k=1, this is a version of the famous secretary problem, and it is well-known that the optimal competitive ratio approaches e as n tends to infinity. Here we prove that for general k, the optimal competitive ratio is 1+O(k-1/2). This leads to a temporally strategyproof online auction mechanism achieving the same competitive ratio when agents arrive in random order.

Adaptive limited-supply online auctions
Mohammad Hajiaghayi, Robert Kleinberg, and David Parkes.
In Proceedings of the 5th ACM Conference on Electronic Commerce (ACM-EC 2004), pages 71-80.
We study online auctions in which the agents arrive and depart over time, and may strategically mis-state the time of their arrival or departure if there is an incentive to do so. Assuming that the agents arrive in random order, we present a constant-competitive strategyproof mechanism for auctioning k identical goods. When k=1, the mechanism can be regarded as a temporally strategyproof modification of the classical algorithm for the "secretary problem."

The value of knowing a demand curve: bounds on regret for on-line posted-price auctions
Robert Kleinberg and Tom Leighton.
In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 594-605.
In an online posted-price auction, a seller interacts with a sequence of buyers by presenting a take-it-or-leave-it offer to each. What is the optimal adaptive price-setting algorithm for this transaction model, and how well does it perform? Stated differently: "What is the value of knowing the demand curve?" We answer this question under three different assumptions on the distribution of the bidders' values for the good: identical, random, or worst-case valuations.

Online Learning and Its Applications

Online learning with global cost functions.
E. Even-Dar, R. Kleinberg, S. Mannor, and Y. Mansour.
To appear in Proceedings of the 22nd Annual Conference on Learning Theory (COLT 2009).
Paper is in preparation. Link coming soon.
We consider an online learning setting where the learner's performance is judged according to a global cost function, e.g. the Lp norm of the combined loss vector. Using approachability theory, we design a general algorithm that guarantees vanishing average regret for this setting, as well as a simple and efficient algorithm for the special case when the cost function is the L norm. We also show that for concave global cost functions, the learner's worst-case average regret does not vanish in general.

The K-armed dueling bandits problem.
Y. Yue, J. Broder, R. Kleinberg, and T. Joachims.
To appear in Proceedings of the 22nd Annual Conference on Learning Theory (COLT 2009).
Paper is in preparation. Link coming soon.
We introduce a variant of the multi-armed bandit problem in which the feedback comes from pairwise comparisons between the arms, rather than choosing a single arm and observing its reward. The problem is motivated by applications such as information retrieval in which users have an easier time comparing two alternatives than estimating the quality of a single choice. We formulate an appropriate notion of regret for this setting, and give an algorithm whose regret is within a constant factor of the information-theoretic optimum.

Learning diverse rankings with multi-armed bandits
F. Radlinski, R. Kleinberg, and T. Joachims.
In Proceedings of the 25th International Conference on Machine Learning (ICML 2008), pp. 784--791.
Algorithms for learning to rank Web documents usually assume a document's relevance is independent of other documents. This leads to learned ranking functions that produce rankings with redundant results. In contrast, user studies have shown that diversity at high ranks is often preferred. We present two online learning algorithms that directly learn a diverse ranking of documents based on users' clicking behavior. We show that these algorithms minimize abandonment, or alternatively, maximize the probability that a relevant document is found in the top k positions of a ranking. Moreover, one of our algorithms asymptotically achieves optimal worst-case performance even if users' interests change.
Regret bounds for sleeping experts and bandits
R. Kleinberg, A. Niculescu-Mizil, and Y. Sharma.
In Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), pp. 425--436.
We study on-line decision problems where the set of actions available to the decision algorithm varies over time. Departing from previous work on this "sleeping experts" problem, we compare algorithms against the payoff obtained by the best ordering of the alternatives, which is a natural benchmark for this type of problem.
Multi-armed bandit problems in metric spaces
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.
In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC 2008), 681-690.
Motivated in part by problems arising in the placement of web advertisements, we study multi-armed bandit problems whose strategy set is a metric space and whose payoff functions satisfy a Lipschitz condition with respect to the metric. We define an isometry-invariant for every metric space — the max-min-covering dimension — which characterizes the performance of the optimal multi-armed bandit algorithm for that metric space, and we present an algorithm which meets this bound. Furthermore, we demonstrate that our technique gives even better results for "benign" payoff functions.

Noisy binary search and its applications
Richard Karp and Robert Kleinberg.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 881-890.
We study a noisy version of the classical binary search problem of inserting an element into its proper place within an ordered sequence by comparing it with elements of the sequence. In the noisy version we can not compare elements directly. Instead, when we compare our element with an element of the sequence, we observe the outcome of an independent coin-toss whose heads probability increases with that element's position in the sequence. We design algorithms for this search problem and prove information-theoretic lower bounds which match up to a constant factor.

Anytime algorithms for multi-armed bandit problems
Robert Kleinberg.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 928-936.
This paper introduces a new criterion for evaluating multi-armed bandit algorithms. The criterion is a relaxation of the notion of regret, and it raises the possibility of designing bandit algorthms which meet non-trivial performance guarantees even when the strategy set is infinite and the cost functions are unconstrained. Instead of comparing the algorithm's expected average cost with that of the best strategy, one compares it with the average cost of the best strategy outside of the top ε fraction of the strategy set, where ε is a parameter unknown to the algorithm. If the difference between the algorithm's cost and this benchmark converges to zero as the number of trials goes to infinity, for all positive ε, we call the algorithm an anytime bandit algorithm. This paper presents examples of anytime bandit algorithms and proves a non-trivial lower bound on their convergence time.

Competitive collaborative learning
Baruch Awerbuch and Robert Kleinberg.
Journal of Computer and System Sciences 74 (2008): 1271-1288, special issue on computational learning theory.
Extended abstract appeared in Proceedings of the 18th Annual Conference on Learning Theory (COLT 2005), pp. 233-248.
How can systems like eBay's reputation system or peer-to-peer resource location protocols be designed to give honest users good advice about selecting products or resources, in spite of potentially misleading information from malicious users? This paper proposes a paradigm for addressing such questions using online learning theory. The model is a generalization of the multi-armed bandit problem, but with multiple users sharing information. An unknown subset of the users are Byzantine adversaries, and the goal is for the remaining users to converge as rapidly as possible to making decisions with low average regret. The main result is an algorithm with polylogarithmic convergence time, assuming a constant fraction of the users are honest.

Provably competitive adaptive routing
Baruch Awerbuch, David Holmer, Herbert Rubens, and Robert Kleinberg.
In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), pp. 631-641.
This paper contains theorems and experimental results concerning an algorithm for learning the most reliable path between two designated terminals in a directed graph with a time-varying pattern of edge failures. The algorithm is allowed to probe only one path in each trial; the feedback from such a trial reveals the location of the first edge failure.

Online linear optimization and adaptive routing
Baruch Awerbuch and Robert Kleinberg.
Journal of Computer and System Sciences, 74(1):97-114. Special issue on computational learning theory, February 2008.
Extended abstract appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pages 45-53.
Motivated by the problem of adaptive routing in overlay networks, we consider the online shortest path problem and its generalization, the online linear optimization problem. Our algorithms work in the partial feedback model, where only the function value at the selected point is revealed. (E.g., only the end-to-end length of the chosen path is revealed.) Our algorithm builds on an elegant algorithm of Kalai and Vempala for solving this problem in the full feedback model, in which the entire cost function is revealed after each trial.

Nearly tight bounds for the continuum-armed bandit problem
Robert Kleinberg.
In Advances in Neural Information Processing Systems 17 (NIPS 2004), pp. 697-704.
In a continuum-armed bandit problem, a learner has a set of strategies parametrized by one or more parameters and must choose one strategy in each of a sequence of trials. In each trial an adversary (or a random sampling process) specifies a function assigning a cost to each strategy, and reveals only the cost of the strategy chosen by the learner. This paper establishes nearly tight bounds on the regret of the optimal algorithm in the one-parameter case. In the multi-parameter case, assuming the cost functions are convex, we present an algorithm achieving polynomial convergence time, based on Zinkevich's online convex programming algorithm.

Online decision problems with large strategy sets
Robert Kleinberg.
Ph.D. Thesis, MIT, 2005.
In an online decision problem, an algorithm performs a sequence of trials, each of which involves selecting one element from a fixed set of alternatives (the "strategy set") whose costs vary over time. After T trials, the combined cost of the algorithm's choices is compared with that of the single strategy whose combined cost is minimum. Their difference is called regret, and one seeks algorithms which are efficient in that their regret is sublinear in T and polynomial in the problem size.

This thesis concerns an important class of online decision problems called generalized multi-armed bandit problems. Most existing algorithms for such problems were efficient only in the case of a small (i.e. polynomial-sized) strategy set. We extend the theory by supplying non-trivial algorithms and lower bounds for cases in which the strategy set is much larger (exponential or infinite) and the cost function class is structured, e.g. by constraining the cost functions to be linear or convex. As applications, we consider adaptive routing in networks, adaptive pricing in electronic markets, and collaborative decision-making by untrusting peers in a dynamic environment.

Routing and Information Transmission in Networks

Online bipartite perfect matching with augmentations
K. Chaudhuri, C. Daskalakis, R. Kleinberg, and H. Lin.
To appear in Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2009).
We study algorithms for maintaining a matching in a bipartite graph describing a set of potential connections between clients and servers. In our model, clients arrive one at a time, revealing their set of adjacent servers at the time of arrival. The graph is assumed to always have at least one matching containing all the clients, and the algorithm maintains such a matching after each client arrival, updating its previous matching using an augmenting path if necessary. The cost of a sequence of updates is the total switching cost, i.e. the total length of all the augmenting paths. We give algorithms achieving total switching cost O(n log n) in trees and in arbitrary graphs with random client arrival order. We also give an algorithm achieving total switching cost O(n) with high probability in random graphs of average degree Θ(log n).

A "chicken and egg" network coding problem
N. Harvey, R. Kleinberg, C. Nair, and Y. Wu.
In Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT 2007).
We consider the multi-source network coding problem in cyclic networks. This problem involves several difficulties not found in acyclic networks, due to additional causality requirements. This paper highlights the difficulty of these causality conditions by analyzing two example cyclic networks which are structurally similar. Both networks have an essentially identical network code which appears to transmit all information from the sources to the sinks; however, this network code is invalid since it violates causality. We show that, in one of the networks, the invalid code can be modified to obey causality, whereas in the other network this is impossible. This unachievability result is proven by a new information inequality for causal coding schemes in a simple cyclic network.
Geographic routing using hyperbolic space
Robert Kleinberg.
In Proceedings of the 26th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2007), pp. 1902-1909.
We study the design of point-to-point routing schemes in ad hoc wireless networks and sensornets based on greedy routing in a virtual coordinate space. We prove that every connected graph may be embedded in the hyperbolic plane in such a way that the greedy routing algorithm succeeds in connecting every sender-receiver pair. We prove that O(log n) dimensions are required to achieve the same property using a normed vector space, and we give a construction which matches this lower bound.
Semi-oblivious routing: lower bounds
MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 929-938.
We initiate the study of semi-oblivious routing, a relaxation of oblivious routing in which an algorithm is given an undirected graph and must select a polynomial number of distinguished paths in the graph so as to route any subsequently-specified demand matrix with approximately optimal congestion while using only the distinguished paths. We prove near-logarithmic lower bounds in this model for grids and series-parallel graphs, and polynomial lower bounds under stronger restrictions on the set of distinguished paths.
On the capacity of information networks
Nicholas Harvey, Robert Kleinberg, and April Rasala Lehman.
Special Issue of the IEEE Transactions on Information Theory and the IEEE/ACM Transactions on Networking, 52(6):2345-2364, June 2006.
We study the maximum concurrent rate of transmission for network coding solutions of k-pairs problems, in which one seeks to simultaneously transmit data streams between k sender-receiver pairs in an edge-capacitated network. The undirected k-pairs conjecture asserts that for k-pairs problems in undirected graphs, the maximum rate achievable by a network coding solution is also achievable by a concurrent multicommodity flow. To make progress on this conjecture, we introduce a technique for proving upper bounds on the network coding rate by combining information-theoretic inequalities (e.g. submodularity of entropy functions) with combinatorial inequalities based on informational dominance, a generalization of the sparsest-cut condition. We demonstrate the power of these techniques by verifying the undirected k-pairs conjecture for an infinite family of non-trivial instances. Finally, turning our attention to k-pairs problems in directed graphs, we give a tight characterization of the largest possible gap between the network coding rate and the maximum concurrent multicommodity flow rate.

An extended abstract announcing a superset of these results appeared in SODA 2006, and is listed below.

Improved lower and upper bounds for universal TSP in planar metrics
Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 649-658.
A universal TSP tour of a metric space is a total ordering of the points of the space such that for any finite subset, the tour which visits these points in the given order is not too much longer than the optimal tour. We prove a super-constant lower bound on the competitive ratio of the best universal TSP tour of an n-by-n grid. When the metric space is the shortest-path metric of a planar graph (or more generally, an H-minor free graph for some fixed graph H), we prove that there exists a universal TSP tour whose competitive ratio is O(log2 n), and we provide a randomized polynomial-time algorithm for computing such a tour.

New lower bounds for oblivious routing in undirected graphs
Mohammad Hajiaghayi, Robert Kleinberg, Tom Leighton, and Harald Racke.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 918-927.
The first half of this paper studies lower bounds for the average-case competitive ratio of oblivious routing in undirected graphs in the random demand model, when the demand for each commodity is sampled independently from a distribution which is known in advance of defining the routing scheme. In this random demand model, we prove two lower bounds on the competitive ratio of the opimal oblivious routing algorithm: Ω(log n / log log n) in the general case, and Ω(log1/2n) in the single-sink case. In the second half of the paper, we introduce a natural measure of the throughput ratio of an oblivious routing scheme, and we prove that the throughput ratio of oblivious routing schemes in expander graphs must be at least Ω(log n / log log n).

On the capacity of information networks
Micah Adler, Nicholas Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 241-250.
A subset of this work appears in the journal paper with the same title, listed above. In addition to the results contained in that paper, we provide evidence for the hardness of the undirected k-pairs conjecture. Specifically, we show that proving the conjecture for general graphs would imply the strongest known lower bounds for the I/O complexity of matrix transposition and for computation in the oblivious cell-probe model, and would imply a non-trivial lower bound for two-tape oblivious Turing computation.

Tighter cut-based bounds for k-pairs communication problems
Nicholas Harvey and Robert Kleinberg.
Invited Paper, 43rd Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, September 2005.
We study the extent to which combinatorial cut conditions determine the maximum network coding rate of k-pairs communication problems in directed graphs. We seek a combinatorial parameter of the network which constitutes a valid upper bound on the network coding rate but whose gap --- the worst-case ratio between the parameter's value and the true maximum network coding rate --- is small. We begin by showing that two parameters proposed earlier, vertex-sparsity and meagerness, have a gap which is linear in the network size. Next we propose a new bound called informational meagerness, which generalizes both vertex-sparsity and meagerness. While it is not known whether informational meagerness has a sublinear gap, we prove here that the gap is at least logarithmic in the network size.

Localized client-server load balancing without global information
Baruch Awerbuch, Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.
SIAM Journal on Computing, 37(4):1259-1279.
Extended abstract appeared in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 197-206.
This paper studies load-balancing algorithms for a network of clients and servers modeled as a bipartite graph. We require the algorithms to satisfy an extremely strict local-control requirement: each participant must make its admission control decisions knowing only the state of its neighbors. This work can be interpreted as a companion to recent work by Racke and others on oblivious routing, but with the objective of maximizing throughput rather than minimizing congestion.

Oblivious routing on node-capacitated and directed graphs
Mohammad Hajiaghayi, Robert Kleinberg, Tom Leighton, and Harald Racke.
ACM Transactions on Algorithms (TALG) 3 (4), November 2007.
Extended abstract appeared in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 782-790.
We study oblivious routing in general directed networks, and in undirected networks with node capacities. We present the first non-trivial upper bounds for both of these problems. We also settle an open question about single-sink (or single-source) oblivious routing problems in undirected edge-capacitated graphs.

(Almost) tight bounds and existence theorems for single-commodity confluent flows
Jiangzhuo Chen, Robert Kleinberg, Laszlo Lovasz, Rajmohan Rajaraman, Ravi Sundaram, and Adrian Vetta.
Journal of the ACM, 54 (4), July 2007. Extended abstract appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pages 529-538.
A confluent flow is a network flow in which each node sends all of its flow along a single outgoing edge. (For example, flows in IP networks are confluent because IP routing is destination-based.) We study two combinatorial optimization problems involving confluent flow: the problem of computing a minimum-congestion confluent flow, and the problem of computing a confluent flow which satisfies the maximum demand subject to hard capacity constraints. Approximation algorithms are given for both problems, as well as hardness proofs showing that both approximation ratios are tight up to a constant factor.

Modeling Complex Networks

On the Internet delay space dimensionality
B. Abrahao and R. Kleinberg.
In Proceedings of the 2008 Internet Measurement Conference (IMC 2008), pp. 157--168.
Brief announcement in Proceedings of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008), p. 419.
For more information including datasets, see the InetDim project page maintained by Bruno Abrahao.
This work investigates the dimensionality properties of the Internet delay space, i.e., the matrix of measured round-trip times between Internet hosts. Our key findings are that fractal measures, such as the correlation fractal dimension and Hausdorff dimension, reveal a dimensionality less than 2, and that the dimensionality is further reduced when one restricts the measurements to subsets composed of a single Tier-1 autonomous system and its downstream customers.
Emergence of tempered preferential attachment from optimization
R. M. D'Souza, C. Borgs, J. T. Chayes, N. Berger, and R. Kleinberg.
Proceedings of the National Academy of Sciences (PNAS), 104 (15): 6112-6117, 2007.
We show how preferential attachment can emerge in an optimization framework, resolving a long-standing theoretical controversy. We also show that the preferential attachment model so obtained has two novel features, saturation and viability, which have natural interpretations in the underlying network and lead to a power-law degree distribution with exponential cutoff. We present a collection of empirical observations from social, biological, physical, and technological networks, for which such degree distributions give excellent fits.

Isomorphism and embedding problems for infinite limits of scale-free graphs
Robert Kleinberg and Jon Kleinberg.
In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 277-286.
The preferential attachment model is a popular random graph process for explaining the structure of large complex networks such as the Internet and World-Wide Web. Here, we study the infinite random graphs which arise as limits of this process, focusing on the questions, "What is the probability that two such graphs are isomorphic?" and, "What finite subgraphs appear in these graphs, and how often do they appear?"

Competition-induced preferential attachment
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D'Souza, and Robert Kleinberg.
To appear in Combinatorics, Probability, and Computing. Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208-221.
We study a network formation model in which preferential-attachment behavior arises as a result of trade-offs between competing proximity measures. In our model, vertices arrive at random locations in a one-dimensional space and join themselves to the network by optimizing a function which trades off two notions of proximity, one defined in terms of the spatial configuration of the points and the other defined in terms of their distances in the network itself.

Computational Algebra

Fast matrix multiplication is stable
James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg.
Numerische Mathematik 106(2):199-224, 2007.
We perform forward error analysis for a large class of recursive matrix multiplication algorithms. As a consequence of our analysis, we show that for every fast matrix multiplication algorithm with running time O(nx) there are numerically stable algorithms with running time O(nx+o(1)). We also show that the new group-theoretic algorithms proposed by Cohn, Kleinberg, Szegedy, and Umans are numerically stable.

Group-theoretic algorithms for matrix multiplication
Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans.
In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 379-388.
We develop fast matrix multiplication algorithms based on the theory of finite group representations, according to the paradigm introduced by Cohn and Umans in 2003. The fastest of these algorithms runs in O(n2.41) operations. We present two conjectures, either of which (if resolved affirmatively) would imply that the exponent of matrix multiplication is equal to 2.

Internet Content Delivery

A transport layer for live streaming in a content delivery network
Leonidas Kontothanassis, Ramesh Sitaraman, Joel Wein, Duke Hong, Robert Kleinberg, Brian Mancuso, David Shaw, and Daniel Stodolsky.
Proceedings of the IEEE, Special Issue on Evolution of Internet Technologies 92(9):1408-1419 (September, 2004).
Designing a system for distibuting streaming media over the Internet poses significant challenges in the areas of scalability, quality, reliability, and cost, among others. In this paper we discuss the design choices made during the evolution of Akamai's Content Delivery Network for streaming media, focusing on design choices made to address these four challenges, and we present the results of performance studies conducted on the evolving system to determine the efficacy of these design choices.

Consistent load balancing via spread minimization
Robert Kleinberg and Tom Leighton.
In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC 2003), pages 565-574.
This paper introduces the spread minimization problem, which is an abstract version of the load-balancing problem faced by systems which seek to use cache resources efficiently over time, e.g. in an Internet content delivery network. We present deterministic offline and randomized online algorithms for this problem, whose worst-case performance is within a constant factor of the optimum assignment's worst-case performance.


Hat guessing games
Steven Butler, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.
SIAM Journal on Discrete Mathematics 22(2):592-605, March 2008.
Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of $n$ players tries to guess the color of the hat they are wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat-guessing problems with a finite number of players.