Home
Contact info
Robert Kleinberg's Publications

SemiOblivious 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. LeytonBrown, and B. Lucier.

In Proc. 26th International Joint Conference on Artificial Intelligence (IJCAI 2017).

Bernoulli Factories and BlackBox 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 11/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 TwoDimensional Schelling Model with Tolerant Individuals

N. Immorlica, R. Kleinberg, B. Lucier, and M. Zadomighaddam.

In Proc. 28th ACMSIAM 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), 124.

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 GameTheoretic 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 NonUniform 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 ACMSIAM Symposium on Discrete Algorithms (SODA 2015).

Building a Secure and PrivacyPreserving Smart Grid

K. Birman, M. Jelasity, R. Kleinberg, and E. Tremel.

SIGOPS Oper. Syst. Rev. 49:1 (2015), 131136.

Simple and NearOptimal 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 (HotNetsXII), 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 TriangleFreeness 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 ACMSIAM 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 SingleParameter Mechanism Design

R. Kleinberg and Y. Yuan.

In Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013).

Multiparameter 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):58115823, 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 PrimalDual Analysis of RANKING for Online
Bipartite Matching

N. R. Devanur, K. Jain, and R. Kleinberg.

In Proceedings of the 24th ACMSIAM 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 st 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 OneDimensional 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 LowDimensional 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 ACMSIAM 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 nonlinear 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).

Continuoustime model of structural balance.

S. Marvel, J. Kleinberg, R. Kleinberg, and S. Strogatz.

Proceedings of the National Academy of Sciences (PNAS)
108 (5): 17711776, 2011.

Bayesian incentive compatibility via matchings.

J. Hartline, R. Kleinberg, and A. Malekian.

In Proceedings of the 22nd ACMSIAM 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. 100114.

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. 111.

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. 178191.

Pricing randomized allocations.

P. Briest, S. Chawla, R. Kleinberg, and S. M. Weinberg.

In Proceedings of the 21st ACMSIAM Symposium on Discrete Algorithms (SODA 2010).

Inapproximability for VCGbased 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 ACMSIAM Symposium on Discrete Algorithms (SODA 2010).

This is a merged paper derived from
Amplified hardness of
approximation for VCGbased 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 ACMSIAM 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. 529536, 2009.

Analyzing quadratic unconstrained binary optimization
problems via multicommodity flows.

D. Wang and R. Kleinberg.

Discrete Applied Mathematics
157 (18): 37463753, 2009.

Online learning with global cost functions.

E. EvenDar, R. Kleinberg, S. Mannor, and Y. Mansour.

In Proceedings of the 22nd Annual
Conference on Learning Theory (COLT 2009).

The Karmed 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): 2129 (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 noregret 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. 157168.

Brief announcement
in Proceedings of the 27th Annual ACM SIGACTSIGOPS 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 localtoglobal characterization of truthfulness

A. Archer and R. Kleinberg.

In Proceedings of the 9th ACM Conference on Electronic Commerce (EC 2008), pp. 2130.

Learning diverse rankings with multiarmed bandits

F. Radlinski, R. Kleinberg, and T. Joachims.

In Proceedings of the 25th International Conference on Machine Learning (ICML 2008), pp. 784791.

Regret bounds for sleeping experts and bandits

R. Kleinberg, A. NiculescuMizil, and Y. Sharma.

Machine Learning 80 (23): 245272, 2010.
(Special Issue on Learning Theory.)

Extended abstract
appeared in Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), pp. 425436.

Multiarmed 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. 681690.

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. 1628.

Automated online mechanism design and prophet inequalities

M. Hajiaghayi, R. Kleinberg, and T. Sandholm.

In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI07), pp. 5865.

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. 103112.

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. 243251.

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): 61126117, 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. 19021909.

Fast matrix multiplication is stable

James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg.

Numerische Mathematik 106(2):199224, 2007.

Matroids, secretary problems, and online mechanisms

Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg.

In Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms (SODA 2007), pp. 434443.

Semioblivious routing: lower bounds

MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.

In Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms (SODA 2007), pp. 929938.

Noisy binary search and its applications

Richard Karp and Robert Kleinberg.

In Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms (SODA 2007), pp. 881890.

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. 389400.

Hat guessing games

Steven Butler, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.

SIAM Journal on Discrete Mathematics 22(2):592605, 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):23452364, June 2006.

Anytime algorithms for multiarmed bandit problems

Robert Kleinberg.

In Proceedings of the 17th ACMSIAM Symposium on Discrete Algorithms (SODA 2006), pp. 928936.

Improved lower and upper bounds for universal TSP in planar metrics

Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.

In Proceedings of the 17th ACMSIAM Symposium on Discrete Algorithms (SODA 2006), pp. 649658.

New lower bounds for oblivious routing in undirected graphs

Mohammad Hajiaghayi, Robert Kleinberg, Tom Leighton, and Harald Racke.

In Proceedings of the 17th ACMSIAM Symposium on Discrete Algorithms (SODA 2006), pp. 918927.

On the capacity of information networks

Micah Adler, Nicholas Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman.

In Proceedings of the 17th ACMSIAM Symposium on Discrete Algorithms (SODA 2006), pp. 241250.

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. 878886.

Grouptheoretic 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. 379388.

Tighter cutbased bounds for kpairs 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): 12711288,
special issue on computational learning theory.

Extended abstract appeared in Proceedings of the 18th Annual Conference on Learning Theory (COLT 2005), pp. 233248.

Online auctions with reusable goods

Mohammad Hajiaghayi, Robert Kleinberg, Mohammad Mahdian, and David Parkes.

In Proceedings of the 6th ACM Conference on Electronic Commerce (EC 2005), pages 165174.

A multiplechoice secretary problem with applications to online auctions

Robert Kleinberg.

In Proceedings of the 16th ACMSIAM Symposium on Discrete Algorithms (SODA 2005), pages 630631.

Localized clientserver load balancing without global information

Baruch Awerbuch, Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.

SIAM Journal on Computing, 37(4):12591279.

Extended abstract appeared
in Proceedings of the 16th ACMSIAM Symposium on Discrete Algorithms (SODA 2005), pages 197206.

Oblivious routing on nodecapacitated 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 ACMSIAM Symposium on Discrete Algorithms (SODA 2005), pages 782790.

Isomorphism and embedding problems for infinite limits of scalefree graphs

Robert Kleinberg and Jon Kleinberg.

In Proceedings of the 16th ACMSIAM Symposium on Discrete Algorithms (SODA 2005), pages 277286.

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. 631641.

Nearly tight bounds for the continuumarmed bandit problem

Robert Kleinberg.

In Advances in Neural Information Processing Systems 17 (NIPS 2004), pp. 697704.

Degree distribution of competitioninduced preferential attachment graphs

Noam Berger, Christian Borgs, Jennifer Chayes, Raissa
D'Souza, and Robert Kleinberg.

Combinatorics, Probability, and Computing 14 (56): 697721.

Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208221.

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):14081419 (September, 2004).

(Almost) tight bounds and existence theorems for singlecommodity 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 529538.

Online linear optimization and adaptive routing

Baruch Awerbuch and Robert Kleinberg.

Journal of Computer and System Sciences, 74(1):97114.
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 4553.

Adaptive limitedsupply online auctions

Mohammad Hajiaghayi, Robert Kleinberg, and David Parkes.

In Proceedings of the 5th ACM Conference on Electronic Commerce (EC 2004), pages 7180.

The value of knowing a demand curve: bounds on
regret for online postedprice auctions

Robert Kleinberg and Tom Leighton.

In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 594605.

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 565574.

Online decision problems with large strategy sets

Robert Kleinberg.

Ph.D. Thesis, MIT, 2005.