Home
Contact info
Robert Kleinberg's Publications
-
Semi-Oblivious Traffic Engineering: The Road Not Taken
-
P. Kumar, Y. Yuan, C. Yu, N. Foster, R. Kleinberg, P. Lapukhov, C. L. Lim, and R. Soulé.
-
To appear in Proc. 15th USENIX Symposium on Networked Systems Design and Implementation
(NSDI 2018).
-
YATES: Rapid prototyping for traffic engineering systems.
-
P. Kumar, Y. Yuan, C. Yu, N. Foster, R. Kleinberg, and R. Soulé.
-
To appear in Proc. 4th Symposium on SDN Research (SOSR 2018).
-
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
-
J. Banks, R. Kleinberg, and C. Moore.
-
In Proc. 20th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM 2017).
-
Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees
-
R. Kleinberg, K. Leyton-Brown, and B. Lucier.
-
In Proc. 26th International Joint Conference on Artificial Intelligence (IJCAI 2017).
-
Bernoulli Factories and Black-Box Reductions in Mechanism Design
-
S. Dughmi, J. Hartline, R. Kleinberg, and R. Niazadeh.
-
In Proc. 49th ACM Symposium on
Theory of Computing (STOC 2017).
-
Beating 1-1/e for Ordered Prophets
-
M. Abolhassani, S. Ehsani, H. Esfandiari, M. T. Hajiaghayi, R. Kleinberg, and B. Lucier.
-
In Proc. 49th ACM Symposium on
Theory of Computing (STOC 2017).
-
Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals
-
N. Immorlica, R. Kleinberg, B. Lucier, and M. Zadomighaddam.
-
In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms
(SODA 2017).
-
Inferential Privacy Guarantees for Differentially Private Mechanisms
-
A. Ghosh and R. Kleinberg.
-
In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017).
-
Job Security, Stability and Production Efficiency
-
H. Fu, R. Kleinberg, R. Lavi, and R. Smorodinsky.
-
Theoretical Economics 12:1 (2017), 1-24.
-
Descending Price Coordinates Approximately Efficient Search
-
R. Kleinberg, B. Waggoner, and E. G. Weyl.
-
In Proceedings of the 17th ACM Conference on Economics and Computation (EC 2016).
-
Simultaneous Nearest Neighbor Search
-
P. Indyk, R. Kleinberg, S. Mahabadi, and Y. Yuan.
-
In Proceedings of the 32nd International Symposium
on Computational Geometry (SOCG 2016).
-
Polymatroid Prophet Inequalities
-
P. Dütting and R. Kleinberg.
-
In Proceedings of the 23rd Annual European Symposium on Algorithms
(ESA 2015).
-
Smooth Online Mechanisms:
A Game-Theoretic Problem in Renewable Energy Markets
-
T. Kesselheim, R. Kleinberg, and É. Tardos.
-
In Proceedings of the 16th Annual ACM Symposium on
Economics and Computation (EC 2015).
-
Secretary Problems with Non-Uniform Arrival Order
-
T. Kesselheim, R. Kleinberg, and R. Niazadeh.
-
In Proceedings of the 47th Annual ACM Symposium on
Theory of Computing (STOC 2015).
-
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
-
S. Dobzinski, H. Fu, and R. Kleinberg.
-
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
-
Building a Secure and Privacy-Preserving Smart Grid
-
K. Birman, M. Jelasity, R. Kleinberg, and E. Tremel.
-
SIGOPS Oper. Syst. Rev. 49:1 (2015), 131-136.
-
Simple and Near-Optimal Mechanisms For Market Intermediation
-
R. Niazadeh, Y. Yuan, and R. Kleinberg.
-
In Proceedings of the 10th Conference on Web and Internet Economics (WINE 2014).
-
Merlin: A Language for Provisioning Network Resources
-
R. Soulé, S. Basu, P. Jalili Marandi, F. Pedone, R. Kleinberg, E. G. Sirer, and N. Foster.
In Proceedings of the 10th Conference on Emerging Networking Experiments and Technologies (CoNEXT 2014).
-
Preliminary version in Proceedings of the 12th ACM Workshop on Hot Topics
in Networking (HotNets-XII), 2013.
-
Incentivizing Exploration
-
P. Frazier, D. Kempe, J. Kleinberg, and R. Kleinberg.
-
In Proceedings of the 15th ACM Conference on Economics and Computation (EC 2014).
-
Behavioral Mechanism Design: Optimal Contests for Simple Agents
-
A. Ghosh and R. Kleinberg.
-
In Proceedings of the 15th ACM Conference on Economics and Computation (EC 2014).
-
Optimal Auctions for Correlated Bidders with Sampling
-
H. Fu, N. Haghpanah, J. Hartline, and R. Kleinberg.
-
In Proceedings of the 15th ACM Conference on Economics and Computation (EC 2014).
-
Improved Lower Bounds for Testing Triangle-Freeness in Boolean Functions via Fast Matrix Multiplication
-
H. Fu and R. Kleinberg.
-
In Approximation, Randomization, and
Combinatorial Optimization.
Algorithms and Techniques (RANDOM 2014).
-
Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications
-
T. Lin, B. Abrahao, R. Kleinberg, J. C. S. Lui, and W. Chen.
-
In Proceedings of the 31st International Conference on Machine Learning (ICML 2014).
-
Prophet Inequalities with Limited Information
-
P. Azar, S. M. Weinberg, and R. Kleinberg.
-
In Proceedings of the 25th ACM-SIAM Symposium on Discrete
Algorithms (SODA 2014).
-
Bandits with Knapsacks
-
A. Badanidiyuru, R. Kleinberg, and A. Slivkins.
-
In Proceedings of the 54th Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2013).
-
Trace Complexity of Network Inference
-
B. Abrahao, F. Chierichetti, R. Kleinberg, and A. Panconesi.
-
In Proceedings of the 19th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining (KDD 2013).
-
On the Ratio of Revenue to Welfare in Single-Parameter Mechanism Design
-
R. Kleinberg and Y. Yuan.
-
In Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013).
-
Multi-parameter Mechanisms with Implicit Payment Computation
-
M. Babaioff, R. Kleinberg, and A. Slivkins.
-
In Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013).
-
Broadcasting with Side Information: Bounding and Approximating the Broadcast Rate
-
A. Blasiak, R. Kleinberg, and E. Lubetzky.
-
IEEE Transactions on Information Theory 59(9):5811-5823, 2013.
-
A Measure of Polarization on Social Media Networks Based on Community Boundaries
-
P. H. Calais Guerra, W. Meira, Jr., C. Cardie, and R. Kleinberg.
-
In Proceedings of the 7th AAAI Conference on Weblogs and Social Media (ICWSM 2013).
-
Randomized Primal-Dual Analysis of RANKING for Online
Bipartite Matching
-
N. R. Devanur, K. Jain, and R. Kleinberg.
-
In Proceedings of the 24th ACM-SIAM Symposium
on Discrete Algorithms (SODA 2013).
-
On the Separability of Structural Classes of Communities
-
B. Abrahao, S. Soundarajan, J. Hopcroft, and R. Kleinberg.
-
In Proceedings of the 18th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining (KDD 2012).
-
Optimal Mechanisms for Selling Information
-
M. Babaioff, R. Kleinberg, and R. Paes Leme.
-
In Proceedings of the 13th Annual ACM Conference on
Electronic Commerce (EC 2012).
-
Conditional Equilibria Via Ascending Price Processes with
Applications to Combinatorial Auctions with Item Bidding
-
H. Fu, R. Kleinberg, and R. Lavi.
-
In Proceedings of the 13th Annual ACM Conference on
Electronic Commerce (EC 2012).
-
Learning on a Budget: Posted Price Mechanisms for Online Procurement
-
A. Badanidiyuru, R. Kleinberg, and Y. Singer.
-
In Proceedings of the 13th Annual ACM Conference on
Electronic Commerce (EC 2012).
-
Dynamic Pricing with Limited Supply.
-
M. Babaioff, S. Dughmi, R. Kleinberg, and A. Slivkins.
-
In Proceedings of the 13th Annual ACM Conference on
Electronic Commerce (EC 2012).
-
Improving Christofides' Algorithm for the s-t Path TSP
-
H.-C. An, R. Kleinberg, and D. B. Shmoys.
-
In Proceedings of the 44th Annual ACM Symposium on
Theory of Computing (STOC 2012).
-
Matroid Prophet Inequalities
-
R. Kleinberg and S. M. Weinberg.
-
In Proceedings of the 44th Annual ACM Symposium on
Theory of Computing (STOC 2012).
-
An Analysis of of One-Dimensional Schelling Segregation
-
C. Brandt, N. Immorlica, G. Kamath, and R. Kleinberg.
-
In Proceedings of the 44th Annual ACM Symposium on
Theory of Computing (STOC 2012).
-
Approximating Low-Dimensional Coverage Problems
-
A. Badanidiyuru, R. Kleinberg, and H. Lee.
-
In Proceedings of the 28th Symposium on Computational
Geometry (SOCG 2012).
-
Sketching valuation functions.
-
A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg,
N. Nisan, and T. Roughgarden.
-
In Proceedings of the 23rd ACM-SIAM Symposium
on Discrete Algorithms (SODA 2012).
-
Which networks are least susceptible to cascading failures?
-
L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, and
É. Tardos.
-
In Proceedings of the 52nd Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2011).
-
Lexicographic products and the power of non-linear network coding.
-
A. Blasiak, R. Kleinberg, and E. Lubetzky.
-
In Proceedings of the 52nd Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2011).
-
Optimal auctions with correlated bidders are easy.
-
S. Dobzinski, H. Fu, and R. Kleinberg.
-
In Proceedings of the 43rd Annual ACM Symposium on
Theory of Computing (STOC 2011).
-
Network formation in the presence of contagious risk.
-
L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, and
É. Tardos.
-
ACM Transactions on Electronic Commerce 1(2), 2013.
Extended abstract appeared in Proceedings of the
12th Annual ACM Conference on Electronic Commerce (EC 2011).
-
Continuous-time model of structural balance.
-
S. Marvel, J. Kleinberg, R. Kleinberg, and S. Strogatz.
-
Proceedings of the National Academy of Sciences (PNAS)
108 (5): 1771-1776, 2011.
-
Bayesian incentive compatibility via matchings.
-
J. Hartline, R. Kleinberg, and A. Malekian.
-
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011).
-
Beyond the Nash equilibrium barrier.
-
R. Kleinberg, K. Ligett, G. Piliouras, and É. Tardos.
-
In Proceedings of the 2nd Symposium on Innovations in Computer
Science (ICS 2011).
-
The serializability of network codes.
-
A. Blasiak and R. Kleinberg.
-
In Proceedings of the 37th International Colloquium on Automata,
Languages, and Programming (ICALP 2010), Track C.
-
Springer
Lecture Notes in Computer Science, Vol. 6199, pp. 100-114.
-
Nonmanipulable randomized tournament selections.
-
A. Altman and R. Kleinberg.
-
In Proceedings of the 24th AAAI Conference on Artificial
Intelligence (AAAI 2010).
-
Truthful mechanisms with implicit payment computation.
-
M. Babaioff, R. Kleinberg, and A. Slivkins.
-
In Proceedings of the 11th Annual ACM Conference
on Electronic Commerce (EC 2010).
-
Approximation algorithms for the bottleneck asymmetric
traveling salesman problem.
-
H.-C. An, R. Kleinberg, and D. Shmoys.
-
In Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques (APPROX 2010).
-
Springer Lecture Notes in Computer
Science, Vol. 6302, pp. 1-11.
-
Improved lower bounds for the universal and a priori TSP.
-
I. Gorodezky, R. Kleinberg, D. Shmoys, and G. Spencer.
-
In Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques (APPROX 2010).
-
Springer Lecture Notes in Computer
Science, Vol. 6302, pp. 178-191.
-
Pricing randomized allocations.
-
P. Briest, S. Chawla, R. Kleinberg, and S. M. Weinberg.
-
In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
-
Inapproximability for VCG-based combinatorial auctions.
-
D. Buchfuhrer, H. Fu, S. Dughmi, R. Kleinberg, E. Mossel, C. Papadimitriou,
M. Schapira, Y. Singer, and C. Umans.
-
In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
-
This is a merged paper derived from
Amplified hardness of
approximation for VCG-based mechanisms
(H. Fu, S. Dughmi, and R. Kleinberg)
and two other papers.
-
Sharp dichotomies for regret minimization in metric spaces.
-
R. Kleinberg and A. Slivkins.
-
In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
-
Randomized online algorithms for the buyback problem.
-
Ashwinkumar B.V. and R. Kleinberg.
-
In Proceedings of the 5th Workshop on Internet
and Network Economics (WINE 2009).
-
Springer
Lecture Notes in Computer Science, Vol. 5929, pp. 529-536, 2009.
-
Analyzing quadratic unconstrained binary optimization
problems via multicommodity flows.
-
D. Wang and R. Kleinberg.
-
Discrete Applied Mathematics
157 (18): 3746-3753, 2009.
-
Online learning with global cost functions.
-
E. Even-Dar, R. Kleinberg, S. Mannor, and Y. Mansour.
-
In Proceedings of the 22nd Annual
Conference on Learning Theory (COLT 2009).
-
The K-armed dueling bandits problem.
-
Y. Yue, J. Broder, R. Kleinberg, and T. Joachims.
-
In Proceedings of the 22nd Annual
Conference on Learning Theory (COLT 2009).
-
Load balancing without regret in the bulletin board model.
-
R. Kleinberg, G. Piliouras, and É. Tardos.
-
Distributed Computing 24(1): 21-29 (2011). (Special issue on selected
papers from PODC 2009.)
-
Extended abstract appeared in Proceedings of the 28th
Symposium on Principles of Distributed Computing (PODC 2009).
-
Selling ad campaigns: Online algorithms with cancellations
-
M. Babaioff, J. D. Hartline, and R. Kleinberg.
-
In Proceedings of the 10th Annual ACM Conference
on Electronic Commerce (EC 2009).
-
Multiplicative updates outperform generic no-regret learning in congestion games
-
R. Kleinberg, G. Piliouras, and É. Tardos.
-
In Proceedings of the 41th ACM Symposium on Theory of Computing (STOC 2009).
-
Online bipartite perfect matching with augmentations
-
K. Chaudhuri, C. Daskalakis, R. Kleinberg, and H. Lin.
-
In Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2009).
-
Characterizing truthful mechanisms with convex type spaces
-
A. Archer and R. Kleinberg.
-
SIGecom Exchanges 7(3), November 2008.
-
Online auctions and generalized secretary problems
-
M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg.
-
SIGecom Exchanges 7(2), June 2008.
-
Selling banner ads: Online algorithms
with buyback
-
M. Babaioff, J. D. Hartline, and R. Kleinberg.
-
Workshop on Ad Auctions 2008, Chicago, Illinois, USA.
-
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.
-
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.
-
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.
-
Regret bounds for sleeping experts and bandits
-
R. Kleinberg, A. Niculescu-Mizil, and Y. Sharma.
-
Machine Learning 80 (2-3): 245-272, 2010.
(Special Issue on Learning Theory.)
-
Extended abstract
appeared in Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), pp. 425-436.
-
Multi-armed bandit problems in metric spaces
-
R. Kleinberg, A. Slivkins, and E. Upfal.
-
In Proceedings of the 40th ACM Symposium on Theory of Computing
(STOC 2008), pp. 681-690.
-
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.
-
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.
-
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).
-
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.
-
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.
-
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.
-
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.
-
Fast matrix multiplication is stable
-
James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg.
-
Numerische Mathematik 106(2):199-224, 2007.
-
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.
-
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.
-
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.
-
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.
-
Hat guessing games
-
Steven Butler, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.
-
SIAM Journal on Discrete Mathematics 22(2):592-605, March 2008.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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 (EC 2005), pages 165--174.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Nearly tight bounds for the continuum-armed bandit problem
-
Robert Kleinberg.
-
In Advances in Neural Information Processing Systems 17 (NIPS 2004), pp. 697-704.
-
Degree distribution of competition-induced preferential attachment graphs
-
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa
D'Souza, and Robert Kleinberg.
-
Combinatorics, Probability, and Computing 14 (5-6): 697-721.
-
Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208-221.
-
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).
-
(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.
-
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.
-
Adaptive limited-supply online auctions
-
Mohammad Hajiaghayi, Robert Kleinberg, and David Parkes.
-
In Proceedings of the 5th ACM Conference on Electronic Commerce (EC 2004), pages 71-80.
-
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.
-
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.
-
Online decision problems with large strategy sets
-
Robert Kleinberg.
-
Ph.D. Thesis, MIT, 2005.