- 1 S. Albers. Better bounds for online scheduling. In Proc. 29th Annual ACM Symp. on Theory of Computing, 130-139, 1997. Google Scholar
- 2 J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the A CM, 44:486-504, 1997. Google Scholar
- 3 B. Awerbuch, Y. Azar and S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symp. on Foundations of Computer Science, 32-40, 1993.Google Scholar
- 4 B. Awerbuch, Y. Bartal, A. Fiat and A. Ros6n. Competitive non-preemptive call control. In Proc. of 5th ACM-SIAM Syrup. on Discrete Algorithms, 312-320, 1994. Google Scholar
- 5 B. Awerbuch, R. Gawlick, T. Leighton and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proc. of the 35th Annual IEEE Syrup. on Foundations of Computer Science, 412-423, 1994.Google Scholar
- 6 Y. Azar, A. Broder and A. Karlin. On-line load balancing. Proc. 36th IEEE Syrup. on Foundations of Computer Science, 218-225, 1992.Google Scholar
- 7 Y. Azar. On-line load balancing. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS 1442, 178-195, 1998. Google Scholar
- 8 Y. Azar and L. Epstein. On-line load balancing with of temporary tasks on identical machines. In Proc. 5th Israeli Syrup. on Theory of Computing and Systems, 119-125, 1997. Google Scholar
- 9 Y. Azar, B. Kalyanasundaram, S. Plotkin. K. Pruhs amd O. Waarts. Online load balancing of temporary tasks. In Proc. of the 3rd Workshop on Algorithms and Data Structures, Springer LNCS, 119-130, 1993. Google Scholar
- 10 Y. Bartal, A. Fiat, H. Karloff and R. Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51:359-366, 1995. Google Scholar
- 11 Y. Bartal, A. Fiat and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In Proc. of the 28th A CM Syrup. on Theory of Computing, 531-540, 1996. Google Scholar
- 12 Y. Bartal and S. Leonardi. On-line routing in all-optical networks. In Proc. of the 2~th International Colloqium on Automata, Languages and Programming, Springer LNCS, Volume 1256, 516-526, 1997. Google Scholar
- 13 S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2-14,1994.Google Scholar
- 14 A. Blum. On-line algorithms in machine learning. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 306-325, 1998. Google Scholar
- 15 A. Borodin and Ran E1-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
- 16 A. Borodin, N. LiniM and M. Saks. An optimal on-line algorithm for metrical task systems. Journal of the ACM, 39:745-763, 1992. Google Scholar
- 17 A. Borodin, S. Irani, P. Raghavan and B. Schieber. Competitive paging with locality of reference. In Proc. 23rd Annual ACM Syrup. on Theory of Computing, 249-259, 1991. Google Scholar
- 18 N. Cesa-Bianchi, Y. Freund, D.P. Helbold, D. Haussler, R.E. Schapire and M.K. Warmuth. How to use expert advice. In Proc. 25th Annual ACM Syrup. on Theory of Computing, 382-391, 1993. Google Scholar
- 19 A. Chou, J. Cooperstock, R. E1 Yaniv, M. Klugerman and T. Leighton. The statistical adversary allows optimal money-making trading strategies. In Proc. 6th Annual ACM- SIAM Syrup. on Discrete Algorithms, 467-476, 1995. Google Scholar
- 20 A. Fiat and A.R. Karlin. Randomized and multipointer paging with locality of reference. In Proc. 27th Annual ACM Syrup. on Theory of Computing, 626-634, 1995. Google Scholar
- 21 A. Fiat and Z. Ros~n. Experimental studies of access graph based heuristics. In Proc. 8th ACM-SIAM Syrup. on Discrete Algorithms, 1997. Google Scholar
- 22 J. Garay, I.S. Gopal, S. Kutten, Y. Mansour and M. Yung. Efficient online call control algorithms. In Proc. 2nd Israel Syrup. on Theory of Computing and Systems, 285-293, 1993.Google Scholar
- 23 R. Gawlick, A. Kamath, S. Plotkin and K. Ramakrishnan. Routing and admission control of virtual circuits in general topology networks. Technical Report BL011212-940819- 19TM ATf~T Bell Laboratories, 1994.Google Scholar
- 24 T. Gormley and E. Torng. Bounded online problems. Manuscript, 1998.Google Scholar
- 25 R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.Google Scholar
- 26 D.S. Hochbaum (Editor). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997. Google Scholar
- 27 S. Irani, A.R. Karlin and S. Phillips. Strongly competitive algorithms for paging with locality of reference. In Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, 228-236, 1992. Google Scholar
- 28 D.R. Karger, S.J. Phillips and E. Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20: 400-430, 1996. Google Scholar
- 29 A. Karlin, M. Manasse, L. Rudolph and D.D. Sleator. Competitive snoopy caching, Algorithmica, 3:79-119, 1988.Google Scholar
- 30 J. Kleinberg and 1~. Tardos. Disjoint paths in densely embedded graphs. In Proc. of the 36th Annual IEEE Symp. on Foundations of Computer Science, 52-61, 1995. Google Scholar
- 31 E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 34th Annual Symp. on Foundations of Computer Science, 394-400, 1994.Google Scholar
- 32 S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti and A. Ros~n. On-line randomized cMl-control revisited. In Proc. of the 9th ACM-SIAM Syrup. on Discrete Algorithms, 223-232, 1998. Google Scholar
- 33 S. Leonardi. On-line network routing. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 242-267, 1998. Google Scholar
- 34 N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Computation, 108:212-261, 1994. Google Scholar
- 35 M.S. Manasse, L.A. McGeoch and D.D. Sleator. Competitive algorithms for on-line problems. In Proc. 20th Annual ACM Symp. on Theory of Computing, 322-33, 1988. Google Scholar
- 36 R. Motwani, S. Phillips and E. Torng. Non-clearvoyant scheduling. Proc. 4th Annual ACM- SIAM Symp. on Discrete Algorithms, 422-431, 1993. Google Scholar
- 37 R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google Scholar
- 38 P. Raghavan. A statistical adversary for on-line algorithms. In On-Line Algorithms, DI- MACS Series in Discrete Mathematics and Theoretical Computer Science, 79-83, 1991.Google Scholar
- 39 J. SgM1. On-line scheduling. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 198-231, 1998.Google Scholar
- 40 D. Shmoys, J. Wein and D.P. Williamson. Scheduling parallel machines on-line. SIAM Journal on Computing 24:1313-1331, 1995. Google Scholar
- 41 D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985. Google Scholar
Recommendations
Divisible On-Line/Off-Line Signatures
CT-RSA '09: Proceedings of the The Cryptographers' Track at the RSA Conference 2009 on Topics in CryptologyOn-line/Off-line signatures are used in a particular scenario where the signer must respond quickly once the message to be signed is presented. The idea is to split the signing procedure into two phases: the off-line and on-line phases. The signer can ...
Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
AbstractIn this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set of n points in the Euclidean plane , we are asked ...
Comments