Arrow Research search

Author name cluster

Jon M. Kleinberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

56 papers
1 author row

Possible papers

56

FOCS Conference 2025 Conference Paper

Density Measures for Language Generation

  • Jon M. Kleinberg
  • Fan Wei

The recent successes of large language models (LLMs) have led to a surge of theoretical research into the properties of language generation. A recent line of work has proposed an abstract view of the question — called language generation in the limit — in which we view language generation as a game played between an adversary and an algorithm: the adversary generates strings from an unknown language K, known only to come from a countable collection of candidate languages, and after observing a finite set of these strings, the algorithm must generate new strings from the language K that it hasn't seen before. This formalism highlights an important tension: the trade-off between validity (that the algorithm should only produce strings that come from the language) and breadth (that the algorithm should be able to produce "many" strings from the language). This validity-breadth trade-off is a central issue in applied work on language generation as well, where it arises in the balance between hallucination, when models generate invalid utterances, and mode collapse, when models only generate from a very restricted set of feasible outputs. Despite its importance, this trade-off has been challenging to study quantitatively. In this work we develop ways of quantifying this trade-off, by formalizing the notion of breadth through measures of density. Roughly speaking, the density of one language L in another language L' is the limiting fraction of strings from L among the strings of L', where we take the limit over longer and longer finite prefixes of L'. Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language K, in this asymptotic sense, and this represents an important failure of breadth that might seem necessary in any solution to the problem. We show here that such a failure is not in fact necessary: we provide an algorithm for language generation in the limit whose outputs have strictly positive density in the true language K. We also study the internal representations built by algorithms for this problem — the sequence of hypothesized candidate languages they iterate through as they perform generation — showing a precise sense in which the strongest form of breadth achievable is one that may need to "oscillate" indefinitely between hypothesized representations of high density and low density. Our analysis introduces a novel topology on language families, with notions of convergence and limit points in this topology playing a key role in the analysis.

Details

ICML Conference 2025 Conference Paper

Sparse Autoencoders for Hypothesis Generation

  • Rajiv Movva
  • Kenny Peng
  • Nikhil Garg 0001
  • Jon M. Kleinberg
  • Emma Pierson

We describe HypotheSAEs, a general method to hypothesize interpretable relationships between text data (e. g. , headlines) and a target variable (e. g. , clicks). HypotheSAEs has three steps: (1) train a sparse autoencoder on text embeddings to produce interpretable features describing the data distribution, (2) select features that predict the target variable, and (3) generate a natural language interpretation of each feature (e. g. , mentions being surprised or shocked ) using an LLM. Each interpretation serves as a hypothesis about what predicts the target variable. Compared to baselines, our method better identifies reference hypotheses on synthetic datasets (at least +0. 06 in F1) and produces more predictive hypotheses on real datasets ( twice as many significant findings), despite requiring 1-2 orders of magnitude less compute than recent LLM-based methods. HypotheSAEs also produces novel discoveries on two well-studied tasks: explaining partisan differences in Congressional speeches and identifying drivers of engagement with online headlines.

Details

ICLR Conference 2024 Conference Paper

Designing Skill-Compatible AI: Methodologies and Frameworks in Chess

  • Karim Hamade
  • Reid McIlroy-Young
  • Siddhartha Sen 0001
  • Jon M. Kleinberg
  • Ashton Anderson

Powerful artificial intelligence systems are often used in settings where they must interact with agents that are computationally much weaker, for example when they work alongside humans or operate in complex environments where some tasks are handled by algorithms, heuristics, or other entities of varying computational power. For AI agents to successfully interact in these settings, however, achieving superhuman performance alone is not sufficient; they also need to account for suboptimal actions or idiosyncratic style from their less-skilled counterparts. We propose a formal evaluation framework for assessing the compatibility of near-optimal AI with interaction partners who may have much lower levels of skill; we use popular collaborative chess variants as model systems to study and develop AI agents that can successfully interact with lower-skill entities. Traditional chess engines designed to output near-optimal moves prove to be inadequate partners when paired with engines of various lower skill levels in this domain, as they are not designed to consider the presence of other agents. We contribute three methodologies to explicitly create skill-compatible AI agents in complex decision-making settings, and two chess game frameworks designed to foster collaboration between powerful AI agents and less-skilled partners. On these frameworks, our agents outperform state-of-the-art chess AI (based on AlphaZero) despite being weaker in conventional chess, demonstrating that skill-compatibility is a tangible trait that is qualitatively and measurably distinct from raw performance. Our evaluations further explore and clarify the mechanisms by which our agents achieve skill-compatibility.

Details

ICLR Conference 2024 Conference Paper

From Graphs to Hypergraphs: Hypergraph Projection and its Reconstruction

  • Yanbang Wang
  • Jon M. Kleinberg

We study the implications of the modeling choice to use a graph, instead of a hypergraph, to represent real-world interconnected systems whose constituent relationships are of higher order by nature. Such a modeling choice typically involves an underlying projection process that maps the original hypergraph onto a graph, and is prevalent in graph-based analysis. While hypergraph projection can potentially lead to loss of higher-order relations, there exists very limited studies on the consequences of doing so, as well as its remediation. This work fills this gap by doing two things: (1) we develop analysis based on graph and set theory, showing two ubiquitous patterns of hyperedges that are root to structural information loss in all hypergraph projections; we also quantify the combinatorial impossibility of recovering the lost higher-order structures if no extra help is provided; (2) we still seek to recover the lost higher-order structures in hypergraph projection, and in light of (1)'s findings we make reasonable assumptions to allow the help of some prior knowledge of the application domain. Under this problem setting, we develop a learning-based hypergraph reconstruction method based on an important statistic of hyperedge distributions that we find. Our reconstruction method is systematically evaluated on 8 real-world datasets under different settings, and exhibits consistently top performance. We also demonstrate benefits of the reconstructed hypergraphs through use cases of protein rankings and link predictions.

Details

UAI Conference 2021 Conference Paper

Stochastic model for sunk cost bias

  • Jon M. Kleinberg
  • Sigal Oren
  • Manish Raghavan
  • Nadav Sklar

We present a novel model for capturing the behavior of an agent exhibiting sunk-cost bias in a stochastic environment. Agents exhibiting sunk-cost bias take into account the effort they have already spent on an endeavor when they evaluate whether to continue or abandon it. We model planning tasks in which an agent with this type of bias tries to reach a designated goal. Our model structures this problem as a type of Markov decision process: loosely speaking, the agent traverses a directed acyclic graph with probabilistic transitions, paying costs for its actions as it tries to reach a target node containing a specified reward. The agent’s sunk cost bias is modeled by a cost that it incurs for abandoning the traversal: if the agent decides to stop traversing the graph, it incurs a cost of $\lambda \cdot C_{sunk}$, where ${\lambda \geq 0}$ is a parameter that captures the extent of the bias and $C_{sunk}$ is the sum of costs already invested. We analyze the behavior of two types of agents: naive agents that are unaware of their bias, and sophisticated agents that are aware of it. Since optimal (bias-free) behavior in this problem can involve abandoning the traversal before reaching the goal, the bias exhibited by these types of agents can result in sub-optimal behavior by shifting their decisions about abandonment. We show that in contrast to optimal agents, it is computationally hard to compute the optimal policy for a sophisticated agent. Our main results quantify the loss exhibited by these two types of agents with respect to an optimal agent. We present both general and topology-specific bounds.

Details

ICML Conference 2019 Conference Paper

Direct Uncertainty Prediction for Medical Second Opinions

  • Maithra Raghu
  • Katy Blumer
  • Rory Sayres
  • Ziad Obermeyer
  • Robert Kleinberg
  • Sendhil Mullainathan
  • Jon M. Kleinberg

The issue of disagreements amongst human experts is a ubiquitous one in both machine learning and medicine. In medicine, this often corresponds to doctor disagreements on a patient diagnosis. In this work, we show that machine learning models can be successfully trained to give uncertainty scores to data instances that result in high expert disagreements. In particular, they can identify patient cases that would benefit most from a medical second opinion. Our central methodological finding is that Direct Uncertainty Prediction (DUP), training a model to predict an uncertainty score directly from the raw patient features, works better than Uncertainty Via Classification, the two step process of training a classifier and postprocessing the output distribution to give an uncertainty score. We show this both with a theoretical result, and on extensive evaluations on a large scale medical imaging application.

Details

ICML Conference 2018 Conference Paper

Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?

  • Maithra Raghu
  • Alex Irpan
  • Jacob Andreas
  • Robert Kleinberg
  • Quoc V. Le
  • Jon M. Kleinberg

Deep reinforcement learning has achieved many recent successes, but our understanding of its strengths and limitations is hampered by the lack of rich environments in which we can fully characterize optimal behavior, and correspondingly diagnose individual actions against such a characterization. Here we consider a family of combinatorial games, arising from work of Erdos, Selfridge, and Spencer, and we propose their use as environments for evaluating and comparing different approaches to reinforcement learning. These games have a number of appealing features: they are challenging for current learning approaches, but they form (i) a low-dimensional, simply parametrized environment where (ii) there is a linear closed form solution for optimal behavior from any state, and (iii) the difficulty of the game can be tuned by changing environment parameters in an interpretable way. We use these Erdos-Selfridge-Spencer games not only to compare different algorithms, but test for generalization, make comparisons to supervised learning, analyse multiagent play, and even develop a self play algorithm.

Details

ICML Conference 2017 Conference Paper

On the Expressive Power of Deep Neural Networks

  • Maithra Raghu
  • Ben Poole
  • Jon M. Kleinberg
  • Surya Ganguli
  • Jascha Sohl-Dickstein

We propose a new approach to the problem of neural network expressivity, which seeks to characterize how structural properties of a neural network family affect the functions it is able to compute. Our approach is based on an interrelated set of measures of expressivity, unified by the novel notion of trajectory length, which measures how the output of a network changes as the input sweeps along a one-dimensional path. Our findings show that: (1) The complexity of the computed function grows exponentially with depth (2) All weights are not equal: trained networks are more sensitive to their lower (initial) layer weights (3) Trajectory regularization is a simpler alternative to batch normalization, with the same performance.

Details

FOCS Conference 2011 Conference Paper

How Bad is Forming Your Own Opinion?

  • David Bindel
  • Jon M. Kleinberg
  • Sigal Oren

A long-standing line of work in economic theory has studied models by which a group of people in a social network, each holding a numerical opinion, can arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals' intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions. By interpreting the repeated averaging as best-response dynamics in an underlying game with natural payoffs, and the limit of the process as an equilibrium, we are able to study the cost of disagreement in these models relative to a social optimum. We provide a tight bound on the cost at equilibrium relative to the optimum, our analysis draws a connection between these agreement models and extremal problems for generalized eigenvalues. We also consider a natural network design problem in this setting, where adding links to the underlying network can reduce the cost of disagreement at equilibrium.

Details

FOCS Conference 2011 Conference Paper

Which Networks are Least Susceptible to Cascading Failures?

  • Lawrence E. Blume
  • David A. Easley
  • Jon M. Kleinberg
  • Robert Kleinberg
  • Éva Tardos

The spread of a cascading failure through a network is an issue that comes up in many domains - in the contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease. Here we study a natural model of threshold contagion: each node v is assigned a numerical threshold ℓ(v) drawn independently from an underlying distribution μ, and v will fail as soon as ℓ(v) of its neighbors fail. Despite the simplicity of the formulation, it has been very challenging to analyze the failure processes that arise from arbitrary threshold distributions; even qualitative questions concerning which graphs are the most resilient to cascading failures in these models have been difficult to resolve. Here we develop a set of new techniques for analyzing the failure probabilities of nodes in arbitrary graphs under this model, and we compare different graphs G according to their μ-risk, defined as the maximum failure probability of any node in G when thresholds are drawn from μ. We find that the space of threshold distributions has a surprisingly rich structure when we consider the risk that these thresholds induce on different graphs: small shifts in the distribution of the thresholds can favor graphs with a maximally clustered structure (i. e. , cliques), those with a maximally branching structure (trees), or even intermediate hybrids.

Details

STOC Conference 2008 Conference Paper

Balanced outcomes in social exchange networks

  • Jon M. Kleinberg
  • Éva Tardos

The study of bargaining has a long history, but many basic settings are still rich with unresolved questions. In particular, consider a set of agents who engage in bargaining with one another,but instead of pairs of agents interacting in isolation,agents have the opportunity to choose whom they want to negotiate with, along the edges of a graph representing social-network relations. The area of network exchange theory in sociology has developed a large body of experimental evidence for the way in which people behave in such network-constrained bargaining situations, and it is a challenging problem to develop models that are both mathematically tractable and in general agreement with the results of these experiments. We analyze a natural theoretical model arising in network exchange theory, which can be viewed as a direct extension of the well-known Nash bargaining solution to the case of multiple agents interacting on a graph. While this generalized Nash bargaining solution is surprisingly effective at picking up even subtle differences in bargaining power that have been observed experimentally on small examples, it has remained an open question to characterize the values taken by this solution on general graphs, or to find an efficient means to compute it. Here we resolve these questions, characterizing the possible values of this bargaining solution, and giving an efficient algorithm to compute the set of possible values. Our result exploits connections to the structure of matchings in graphs, including decomposition theorems for graphs with perfect matchings, and also involves the development of new techniques. In particular, the values we are seeking turn out to correspond to a novel combinatorially defined point in the interior of a fractional relaxation of the matching problem.

Details

FOCS Conference 2005 Conference Paper

An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs

  • Jon M. Kleinberg

In joint work with Eva Tardos in 1995, we asked whether it was possible to obtain a polynomial-time, polylogarithmic approximation algorithm for the disjoint paths problem in the class of all even-degree planar graphs. This paper answers the question in the affirmative, by providing such an algorithm. The algorithm builds on recent work of C. Chekuri et al. (2004, 2005), who considered muting problems in planar graphs where each edge can carry up to two paths.

Details

FOCS Conference 2005 Conference Paper

Metric Embeddings with Relaxed Guarantees

  • Ittai Abraham
  • Yair Bartal
  • T. -H. Hubert Chan
  • Kedar Dhamdhere
  • Anupam Gupta 0001
  • Jon M. Kleinberg
  • Ofer Neiman
  • Aleksandrs Slivkins

We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler (2004), we show that provable guarantees of this type can in fact be achieved in general: any finite metric can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into /spl lscr//sub 1/ which exhibit gracefully degrading distortion: these is a single embedding into /spl lscr//sub 1/ that achieves distortion at most O(log 1//spl epsi/) on all but at most an /spl epsi/ fraction of distances, simultaneously for all /spl epsi/ > 0. We extend this with distortion O(log 1//spl epsi/)/sup 1/p/ to maps into general /spl lscr//sub p/, p /spl ges/ 1 for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight, and give a general technique to obtain lower bounds for /spl epsi/-slack embeddings from lower bounds for low-distortion embeddings.

Details

FOCS Conference 2005 Conference Paper

On Learning Mixtures of Heavy-Tailed Distributions

  • Anirban Dasgupta 0001
  • John E. Hopcroft
  • Jon M. Kleinberg
  • Mark Sandler 0002

We consider the problem of learning mixtures of arbitrary symmetric distributions. We formulate sufficient separation conditions and present a learning algorithm with provable guarantees for mixtures of distributions that satisfy these separation conditions. Our bounds are independent of the variances of the distributions; to the best of our knowledge, there were no previous algorithms known with provable learning guarantees for distributions having infinite variance and/or expectation. For Gaussians and log-concave distributions, our results match the best known sufficient separation conditions by D. Achlioptas and F. McSherry (2005) and S. Vempala and G. Wang (2004). Our algorithm requires a sample of size O/spl tilde/(dk), where d is the number of dimensions and k is the number of distributions in the mixture. We also show that for isotropic power-laws, exponential, and Gaussian distributions, our separation condition is optimal up to a constant factor.

Details

FOCS Conference 2005 Conference Paper

Query Incentive Networks

  • Jon M. Kleinberg
  • Prabhakar Raghavan

The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding networks of interacting agents as economic systems. Here we formulate a model for query incentive networks, motivated by such systems: users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. In such systems, it is a fundamental question to understand how much incentive is needed in order for a node to achieve a reasonable probability of obtaining an answer to a query from the network. We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Details

FOCS Conference 2004 Conference Paper

The Price of Stability for Network Design with Fair Cost Allocation

  • Elliot Anshelevich
  • Anirban Dasgupta 0001
  • Jon M. Kleinberg
  • Éva Tardos
  • Tom Wexler
  • Tim Roughgarden

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions - the Nash equilibria - may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context - it is the optimal solution that can be proposed from which no user will "defect". We consider the price of stability for network design with respect to one of the most widely-studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value, and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is O(log k), where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

Details

FOCS Conference 2004 Conference Paper

Triangulation and Embedding Using Small Sets of Beacons

  • Jon M. Kleinberg
  • Aleksandrs Slivkins
  • Tom Wexler

Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. Here we give algorithms with provable performance guarantees for beacon-based triangulation and embedding. We show that in addition to multiplicative error in the distances, performance guarantees for beacon-based algorithms typically must include a notion of slack - a certain fraction of all distances may be arbitrarily distorted. For metrics of bounded doubling dimension (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based reconstruction with a constant number of beacons can achieve multiplicative error 1 + /spl delta/ on a 1 - /spl epsiv/ fraction of distances, for arbitrarily small constants /spl delta/ and /spl epsiv/. For this same class of metrics, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 - /spl epsiv/ fraction of distances; this provides some theoretical justification for the success of the recent global network positioning algorithm of Ng and Zhang, and it forms an interesting contrast with lower bounds showing that it is not possible to embed all distances in a doubling metric with constant distortion. We also give results for other classes of metrics, as well as distributed algorithms that require only a sparse set of distances but do not place too much measurement load on any one node.

Details

FOCS Conference 2002 Conference Paper

Protocols and Impossibility Results for Gossip-Based Communication Mechanisms

  • David Kempe 0001
  • Jon M. Kleinberg

In recent years, gossip-based algorithms have gained prominence as a methodology for designing robust and scalable communication schemes in large distributed systems. The premise underlying distributed gossip is very simple: in each time step, each node v in the system selects some other node w as a communication partner, generally by a simple randomized rule, and exchanges information with w; over a period of time, information spreads through the system in an "epidemic fashion". A fundamental issue which is not well understood is the following: how does the underlying low-level gossip mechanism (the means by which communication partners are chosen) affect one's ability to design efficient high-level gossip-based protocols? We establish one of the first concrete results addressing this question, by showing a fundamental limitation on the power of the commonly used uniform gossip mechanism for solving nearest-resource location problems. In contrast, very efficient protocols for this problem can be designed using a non-uniform spatial gossip mechanism, as established in earlier work with Alan Demers. We go on to consider the design of protocols for more complex problems, providing an efficient distributed gossip-based protocol for a set of nodes in Euclidean space to construct an approximate minimum spanning tree. Here too, we establish a contrasting limitation on the power of uniform gossip for solving this problem. Finally, we investigate gossip-based packet routing as a primitive that underpins the communication patterns in many protocols, and as a way to understand the capabilities of different gossip mechanisms at a general level.

Details

STOC Conference 2001 Conference Paper

Spatial gossip and resource location protocols

  • David Kempe 0001
  • Jon M. Kleinberg
  • Alan J. Demers

The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches. In many settings --- consider a network of sensors, or a cluster of distributed computing hosts --- new information is generated at individual nodes, and is most “interesting” to nodes that are nearby. Thus, we propose distance-based propagation bounds as a performance measure for gossip algorithms: a node at distance d from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with d , and is independent of the size of the network. For nodes arranged with uniform density in Euclidean space, we present natural gossip algorithms that satisfy such a guarantee: new information is spread to nodes at distance \DIST, with high probability, in O(\log^{1 + \ve} \DIST) time steps. Such a bound combines the desirable qualitative features of uniform gossip , in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding , in which information is spread with a delay that is linear in the distance and independent of the network size. Our algorithms and their analysis resolve a conjecture of Demers et al. We show an application of our gossip algorithms to a basic resource location problem , in which nodes seek to rapidly

Details

FOCS Conference 2000 Conference Paper

Detecting a Network Failure

  • Jon M. Kleinberg

Measuring the properties of a large, unstructured network can be difficult: one may not have full knowledge of the network topology, and detailed global measurements may be infeasible. A valuable approach to such problems is to take measurements from selected locations within the network and then aggregate them to infer large-scale properties. One sees this notion applied in settings that range from Internet topology discovery tools to remote software agents that estimate the download times of popular Web pages. Some of the most basic questions about this type of approach, however, are largely unresolved at an analytical level. How reliable are the results? How much does the choice of measurement locations affect the aggregate information one infers about the network? We describe algorithms that yield provable guarantees for a particular problem of this type: detecting a network failure. Suppose we want to detect events of the following form: an adversary destroys up to k nodes or edges, after which two subsets of the nodes, each at least an /spl epsi/ fraction of the network, are disconnected from one another. We call such an event an (/spl epsi/, k) partition. One method for detecting such events would be to place "agents" at a set D of nodes, and record a fault whenever two of them become separated from each other. To be a good detection set, D should become disconnected whenever there is an (/spl epsi/, k)-partition; in this way, it "witnesses" all such events. We show that every graph has a detection set of size polynomial in k and /spl epsi//sup -1/, and independent of the size of the graph itself. Moreover, random sampling provides an effective way to construct such a set. Our analysis establishes a connection between graph separators and the notion of VC-dimension, using techniques based on matchings and disjoint paths.

Details

FOCS Conference 2000 Conference Paper

Fairness Measures for Resource Allocation

  • Amit Kumar 0001
  • Jon M. Kleinberg

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of "global" approximation guarantee, and we explore its consequences in a range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue-one not encountered in the traditional design of approximation algorithms-is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of basic problems in resource allocation, and on the structure of their feasible solutions.

Details

FOCS Conference 1999 Conference Paper

Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields

  • Jon M. Kleinberg
  • Éva Tardos

In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry: and document analysis. In its most basic form, this style of analysis seeks a classification that optimizes a combinatorial function consisting of assignment costs-based on the individual choice of label we make for each object-and separation costs-based on the pair of choices we make for two "related" objects. We formulate a general classification problem of this type, the metric labeling problem; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem. We provide the first non-trivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O(log k log log k)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric-all distances are the same-our methods provide a 2-approximation.

Details

FOCS Conference 1999 Conference Paper

Fairness in Routing and Load Balancing

  • Jon M. Kleinberg
  • Yuval Rabani
  • Éva Tardos

We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria interacts in a complex fashion with the optimization of network utilization and throughput; in this work, we undertake an investigation of this relationship through the framework of approximation algorithms. In this work we consider the problem of selecting paths for routing so as to provide a bandwidth allocation that is as fair as possible (in the max-min sense). We obtain the first approximation algorithms for this basic optimization problem, for single-source unsplittable routings in an arbitrary directed graph. Special cases of our model include several fundamental load balancing problems, endowing them with a natural fairness criterion to which our approach can be applied. Our results form an interesting counterpart to the work of Megiddo (1974), who considered max-min fairness for single-source fractional flow. The optimization problems in our setting become NP-complete, and require the development of new techniques for relating fractional relaxations of routing to the equilibrium constraints imposed by the fairness criterion.

Details

FOCS Conference 1997 Conference Paper

Storage Management for Evolving Databases

  • Jon M. Kleinberg
  • Rajeev Motwani 0001
  • Prabhakar Raghavan
  • Suresh Venkatasubramanian

The problem of maintaining data that arrives continuously over time is increasingly prevalent in databases and digital libraries. Building on a model for sliding window indices developed by N. Shivakumar and H. Garcia-Molina (1997), we devise efficient algorithms for some of the central problems that arise. We also show connections between the problems in this model and some fundamental problems in optimization and graph theory.

Details

FOCS Conference 1996 Conference Paper

Short Paths in Expander Graphs

  • Jon M. Kleinberg
  • Ronitt Rubinfeld

Graph expansion has proved to be a powerful general tool for analyzing the behavior of routing algorithms and the inter-connection networks on which they run. We develop new routing algorithms and structural results for bounded-degree expander graphs. Our results are unified by the fact that they are all based upon, and extend, a body of work: asserting that expanders are rich in short, disjoint paths. In particular, our work has consequences for the disjoint paths problem, multicommodity flow, and graph minor containment. We show: (i) A greedy algorithm for approximating the maximum disjoint paths problem achieves a polylogarithmic approximation ratio in bounded-degree expanders. Although our algorithm is both deterministic and on-line, its performance guarantee is an improvement over previous bounds in expanders. (ii) For a multicommodity flow problem with arbitrary demands on a bounded-degree expander there is a (1+/spl epsi/)-optimal solution using only flow paths of polylogarithmic length. It follows that the multicommodity flow algorithm of Awerbuch and Leighton runs in nearly linear time per commodity in expanders. Our analysis is based on establishing the following: given edge weights on an expander G, one can increase some of the weights very slightly so the resulting shortest-path metric is smooth-the min-weight path between any pair of nodes uses a polylogarithmic number of edges. (iii) Every bounded-degree expander on n nodes contains every graph with O(n/log/sup 0(1)/n) nodes and edges as a minor.

Details

FOCS Conference 1996 Conference Paper

Single-Source Unsplittable Flow

  • Jon M. Kleinberg

The max-flow min-cut theorem of Ford and Fulkerson is based on an even more foundational result, namely Menger's theorem on graph connectivity Menger's theorem provides a good characterization for the following single-source disjoint paths problem: given a graph G, with a source vertex s and terminals t/sub 1/, .. ., t/sub k/, decide whether there exist edge-disjoint s-t/sub i/ paths for i=1, .. ., k. We consider a natural, NP-hard generalization of this problem, which we call the single-source unsplittable flow problem. We are given a source and terminals as before; but now each terminal t/sub i/ has a demand p/sub i//spl les/1, and each edge e of G has a capacity c/sub e//spl ges/1. The problem is to decide whether one can choose a single s-t/sub i/ path for each i, so that the resulting set of paths respects the capacity constraints-the total amount of demand routed across any edge e must be bounded by the capacity c/sub e/. The main results of this paper are constant-factor approximation algorithms for three natural optimization versions of this problem, in arbitrary directed and undirected graphs. The development of these algorithms requires a number of new techniques for rounding fractional solutions to network flow problems; for two of the three problems we consider, there were no previous techniques capable of providing an approximation in the general case, and for the third, the randomized rounding algorithm of Raghavan and Thompson provides a logarithmic approximation. Our techniques are also of interest from the perspective of a family of NP-hard load balancing and machine scheduling problems that can be reduced to the single-source unsplittable flow problem.

Details

FOCS Conference 1996 Conference Paper

Universal Stability Results for Greedy Contention-Resolution Protocols

  • Matthew Andrews
  • Baruch Awerbuch
  • Antonio Fernández 0001
  • Jon M. Kleinberg
  • Frank Thomson Leighton
  • Zhiyong Liu 0002

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

Details

FOCS Conference 1995 Conference Paper

Disjoint Paths in Densely Embedded Graphs

  • Jon M. Kleinberg
  • Éva Tardos

We consider the following maximum disjoint paths problem (MDPP). We are given a large network, and pairs of nodes that wish to communicate over paths through the network-the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem has been brought into focus recently in papers discussing applications to routing in high-speed networks, where the current lack of understanding of the MDPP is an obstacle to the design of practical heuristics. We consider the class of densely embedded, nearly-Eulerian graphs, which includes the two-dimensional mesh and other planar and locally planar interconnection networks. We obtain a constant-factor approximation algorithm for the maximum disjoint paths problem for this class of graphs; this improves on an O(log n)-approximation for the special case of the two-dimensional mesh due to Aumann-Rabani and the authors. For networks that are not explicitly required to be "high-capacity, " this is the first constant-factor approximation for the MDPP in any class of graphs other than trees. We also consider the MDPP in the on-line setting, relevant to applications in which connection requests arrive over time and must be processed immediately. Here we obtain an asymptptically optimal O(log n)competitive on-line algorithm for the same class of graphs; this improves on an O(log n log log n) competitive algorithm for the special case of the mesh due to B. Awerbuch et al (1994).

Details

FOCS Conference 1994 Conference Paper

The Localization Problem for Mobile Robots

  • Jon M. Kleinberg

A fundamental task for an autonomous mobile robot is that of localization-determining its location in a known environment. This problem arises in settings that range from the computer analysis of aerial photographs to the design of autonomous Mars rovers. L. Guibas et al. ((1992) have given geometric algorithms for the problem of enumerating locations for a robot consistent with a given view of the environment. We provide an on-line algorithm for a robot to move within its environment so as to uniquely determine its location. The algorithm improves asymptotically on strategies based purely on the "spiral search" technique of R. Baeza-Yates et al. (1993); an interesting feature of our approach is the way in which the robot is able to identify "critical directions" in the environment which allow it to perform late stages of the search more efficiently. >

Details