ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
On the power of randomization in online algorithms
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents
Baltimore, Maryland, United States
Pages: 379 - 386  
Year of Publication: 1990
ISBN:0-89791-361-2
Authors
S. Ben-David
A. Borodin
R. Karp
G. Tardos
A. Wigderson
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 45
Additional Information:

cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100268
What is a DOI?

CITED BY  45
Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada
Avrim Blum , Prasad Chalasani, Learning switching concepts, Proceedings of the fifth annual workshop on Computational learning theory, p.231-242, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Luca Becchetti , Stefano Leonardi, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.94-103, July 2001, Hersonissos, Greece
Elias Koutsoupias , Christos Papadimitriou, On the k-server conjecture, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.507-511, May 23-25, 1994, Montreal, Quebec, Canada
Miklos Ajtai , James Aspnes , Moni Naor , Yuval Rabani , Leonard J. Schulman , Orli Waarts, Fairness in scheduling, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.477-485, January 22-24, 1995, San Francisco, California, United States
Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States
Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992
Ran El-Yaniv, Competitive solutions for online financial problems, ACM Computing Surveys (CSUR), v.30 n.1, p.28-69, March 1998
E. F. Grove, The harmonic online K-server algorithm is competitive, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.260-266, May 05-08, 1991, New Orleans, Louisiana, United States
Sandy Irani , Nick Reingold , Jeffery Westbrook , Daniel D. Sleator, Randomized competitive algorithms for the list update problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.251-260, January 28-30, 1991, San Francisco, California, United States
Avrim Blum , Prabhakar Raghavan , Baruch Schieber, Navigating in unfamiliar geometric terrain, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.494-504, May 05-08, 1991, New Orleans, Louisiana, United States
Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada
Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States
Piotr Berman , Avrim Blum , Amos Fiat , Howard Karloff , Adi Rosén , Michael Saks, Randomized robot navigation algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.75-84, January 28-30, 1996, Atlanta, Georgia, United States
Xiaotie Deng , Sanjeev Mahajan, Infinite games: randomization, computability, and applications to online problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.289-298, May 05-08, 1991, New Orleans, Louisiana, United States
Marek Chrobak , Lawrence L. Larmore, Generosity helps, or an 11–competitive algorithm for three servers, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.196-202, September 1992, Orlando, Florida, United States
Don Coppersmith , Peter Doyle , Prabhakar Raghavan , Marc Snir, Random walks on weighted graphs and applications to on-line algorithms, Journal of the ACM (JACM), v.40 n.3, p.421-453, July 1993
Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
Todd Gormley , Nicholas Reingold , Eric Torng , Jeffery Westbrook, Generating adversaries for request-answer games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.564-565, January 09-11, 2000, San Francisco, California, United States
Matthias Westermann, Distributed caching independent of the network size, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada
James Aspnes , William Hurwood, Spreading rumors rapidly despite an adversary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States
Bala Kalyanasundaram , Kirk Pruhs, On-line weighted matching, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.234-240, January 28-30, 1991, San Francisco, California, United States
Prasad Tetali, Design of on-line algorithms using hitting times, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.402-411, January 23-25, 1994, Arlington, Virginia, United States
Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States
Yossi Azar , Joseph Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
Yair Bartal , Moses Charikar , Piotr Indyk, On page migration and other relaxed task systems, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.43-52, January 05-07, 1997, New Orleans, Louisiana, United States
M. Bern , D. H. Greene , A. Raghunathan , M. Sudan, Online algorithms for locating checkpoints, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.359-368, May 13-17, 1990, Baltimore, Maryland, United States
D. Coppersmith , P. Doyle , P. Raghavan , M. Snir, Random walks on weighted graphs, and applications to on-line algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.369-378, May 13-17, 1990, Baltimore, Maryland, United States
Allan Borodin, Can competitive analysis be made competitive?, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
Stefano Leonardi , Alberto Marchetti-Spaccamela , Alessio Presciutti , Adi Rosén, On-line randomized call control revisited, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 25-27, 1998, San Francisco, California, United States
A new lower bound for the list update problem in the partial cost model, Theoretical Computer Science, v.268 n.1, p.3-16, 10/06/2001
Michael G. Luby , Joseph (Seffi) Naor , Ariel Orda, Tight bounds for dynamic storage allocation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.724-732, January 23-25, 1994, Arlington, Virginia, United States
Marcin Bienkowski , Miroslaw Korzeniowski , Friedhelm Meyer auf der Heide, Fighting against two adversaries: page migration in dynamic networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
D. M. Yellin, Competitive algorithms for the dynamic selection of component implementations, IBM Systems Journal, v.42 n.1, p.85-97, January 2003
Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Information and Computation, v.185 n.1, p.1-40, August 25, 2003
Rudolf Fleischer , Włodzimierz Głazek , Steve Seiden, New results for online page replication, Theoretical Computer Science, v.324 n.2-3, p.219-251, 20 September 2004
Marcin Bienkowski, Dynamic page migration with stochastic requests, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
Shahram Esmaeilsabzali , Nancy A. Day, Online pricing for web service providers, Proceedings of the 2006 international workshop on Economics driven software engineering research, May 27-27, 2006, Shanghai, China
Weimin Ma , James N. Liu , Guoqing Chen , Jane You, Competitive Analysis for the On-line Truck Transportation Problem, Journal of Global Optimization, v.34 n.4, p.489-502, April 2006
Weimin Ma , Jane You , Yinfeng Xu , James Liu , Kanliang Wang, On the On-line Number of Snacks Problem, Journal of Global Optimization, v.24 n.4, p.449-462, December 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)


General Terms:
Algorithms, Performance

Collaborative Colleagues:
S. Ben-David: colleagues
A. Borodin: colleagues
R. Karp: colleagues
G. Tardos: colleagues
A. Wigderson: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player