Article

Free access

Patience is a virtue: the effect of slack on competitiveness for admission control

Author:

Michael H. GoldwasserAuthors Info & Claims

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

Pages 396 - 405

Published: 01 January 1999 Publication History

PDF eReader

References

[1]

B. Awerbuch: Y. Azar, and S. Plotkin. Throughputcompetitive online routing. In Proceedings of the 33rd Symposium on Foundations of Computer Science, pages 32--40, 1993.

Google Scholar

[2]

B. Awerbuch, Y. Bartal, A. Fiat, and A. Ros#n. Competitive non-preemptive call control. In Proceedings of the Fifth Annual A CM-SIAM Symposium on Discrete Algorithms, pages 312-320, 1994.

Digital Library

Google Scholar

[3]

A. Bar-Noy, R. Canetti, S. Kutten, Y. Mansour, and B. Schiber. Bandwidth allocation with preemption. In Proceedings of the #7th A CM Symposium on Theory of Computing, pages 616-625, 1995.

Digital Library

Google Scholar

[4]

A. Bar-Noy, J. A. Garay, A. Herzberg, and S. Aggarwal. Sharing video on demand. Manuscript, 1998. Presented at the Workshop on Algorithmic Aspects of Communication, Bologna, Italy, July 1997.

Google Scholar

[5]

S. Baruah, G. Koren, D. Mao, B. Mishra, A. Ragunathan, L. Rosier, D. Shasta, and F. Wang. On the competitiveness of on-line real-time task scheduling. In Proceedings of t.he Real-Time Systems Symposium, pages 106-115, 1991.

Google Scholar

[6]

S. K. Baruah and J. R. Harista. Scheduling for overload in real-time systems. IEEE Transactions on Computers, 46(9):1034-1039, 1997.

Digital Library

Google Scholar

[7]

S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Widgerson. On the power of randomization in online algorithms. Algorithmica, 11(1):2-14, 1994.

Google Scholar

[8]

A. Feldmann, B. Maggs, J. Sgall, D. Sleator, and A. Tomkins. Competitive analysis of call admission algorithms that allow delay. Technical Report CMU-CS- 95-102, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1995.

Google Scholar

[9]

J. Garey, I. Gopal, and S. Kutten. Efficient online call control algorithms. Journal of Algorithms, 23(1):180- 194, 1997.

Digital Library

Google Scholar

[10]

S. Goldman, J. Parwatikar, and S. Suri. On-line scheduling with hard deadlines. In Proceedings of the Workshop on Algorithms and Data Structures, volume 1272 of Lecture Notes in Computer Science, pages 258- 271. Springer-Voting, 1997.

Digital Library

Google Scholar

[11]

R. Graham, E. L. Lawler, J. K. Lenstra, and A. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. In D/screte Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287-326. North Holland, 1979.

Google Scholar

[12]

B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. In Proceedings of the 36th Symposium on Foundations of Computer Science, pages 214- 221, 1995.

Digital Library

Google Scholar

[13]

A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy paging. Algorithmic.a, 3(1):70-- 119, 1988.

Google Scholar

[14]

H. Kopetz. Real-time Systems: Design Principles for Distributed Embedded Applicationz. Kluwer Academic Publishers, Boston, 1997.

Digital Library

Google Scholar

[15]

E.L. Lawler, J. K. Lenstra, A. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. Grave#;, A. Rinnooy Kan, and P. Zipken, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, pages 445-522. North Holland, 1993.

Google Scholar

[16]

R. Lipton and A. Tomkins. Online interval scheduling. In Proceedings of the Fifth Annual A CM-SIAM Symposium on Discrete Algorithms, pages 302-311, 1994.

Digital Library

Google Scholar

[17]

D. Long and M. Thakur. Scheduling realtime disk transfers for continuous media applications. In Proceedings of the l$th IEEE Symposium on Mass Storage Systems, pages 227-232, 1993.

Google Scholar

[18]

S. A. Plotkin. Competitive routing of virtual circuits in ATM networks. IEEE Journal on Selected Areas in Communication, 13(6):1128-1136, 1995.

Digital Library

Google Scholar

[19]

P. Raghavan and M. Snir. Memory versus randomization in on-line algorithms. IBM Journal of Research and Development, 38:683-707, 1994.

Digital Library

Google Scholar

[20]

D. Sleator and R. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985.

Digital Library

Google Scholar

Cited By

View all

Ding JZhang G(2006)Online scheduling with hard deadlines on parallel machinesProceedings of the Second international conference on Algorithmic Aspects in Information and Management10.1007/11775096_5(32-42)Online publication date: 20-Jun-2006
https://dl.acm.org/doi/10.1007/11775096_5
Hung RTing H(2006)Design and analysis of online batching systemsProceedings of the 7th Latin American conference on Theoretical Informatics10.1007/11682462_56(605-616)Online publication date: 20-Mar-2006
https://dl.acm.org/doi/10.1007/11682462_56
Palis M(2005)The Granularity Metric for Fine-Grain Real-Time SchedulingIEEE Transactions on Computers10.1109/TC.2005.20454:12(1572-1583)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1109/TC.2005.204
Show More Cited By

Index Terms

Patience is a virtue: the effect of slack on competitiveness for admission control

Recommendations

Note-Patience is a Virtue in a Simple Model of Repetitively Joining a Queue

Each of n members of a finite customer population must weigh the rewards of service completion against the cost of waiting in a single exponential server queuing system. After completing service, a customer may re-enter the system. In attempting to ...
QBD approximations of a call center queueing model with general patience distribution

This paper investigates a computationally practical way for analyzing a call center queueing model, i.e., a finite-capacity, multi-server queueing model, where each server goes on a single vacation. Poisson arrival process and exponential service and ...
A Unified Approach to Diffusion Analysis of Queues with General Patience-Time Distributions

We propose a unified approach to establishing diffusion approximations for queues with impatient customers within a general framework of scaling customer patience time. The approach consists of two steps. The first step is to show that the diffusion-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

January 1999

992 pages

ISBN:0898714346

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1999

Check for updates

Qualifiers

Article

Conference

SODA99

Sponsor:

SIGACT
SIAM

SODA99: 1999 10th Conference on Discrete Algorithms

January 17 - 19, 1999

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
52
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)9

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ding JZhang G(2006)Online scheduling with hard deadlines on parallel machinesProceedings of the Second international conference on Algorithmic Aspects in Information and Management10.1007/11775096_5(32-42)Online publication date: 20-Jun-2006
https://dl.acm.org/doi/10.1007/11775096_5
Hung RTing H(2006)Design and analysis of online batching systemsProceedings of the 7th Latin American conference on Theoretical Informatics10.1007/11682462_56(605-616)Online publication date: 20-Mar-2006
https://dl.acm.org/doi/10.1007/11682462_56
Palis M(2005)The Granularity Metric for Fine-Grain Real-Time SchedulingIEEE Transactions on Computers10.1109/TC.2005.20454:12(1572-1583)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1109/TC.2005.204
Miyazawa HErlebach T(2004)An Improved Randomized On-Line Algorithm for a Weighted Interval Selection ProblemJournal of Scheduling10.1023/B:JOSH.0000031423.39762.d37:4(293-311)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1023/B%3AJOSH.0000031423.39762.d3
Lee JRosenberg AMeyer auf der Heide F(2003)Online deadline schedulingProceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures10.1145/777412.777416(19-23)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/777412.777416
Bar-Yehuda RHalldórsson MNaor JShachnai HShapira IEppstein D(2002)Scheduling split intervalsProceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/545381.545479(732-741)Online publication date: 6-Jan-2002
https://dl.acm.org/doi/10.5555/545381.545479
Bar-Noy AGuha SNaor JSchieber BVitter JLarmore LLeighton T(1999)Approximating the throughput of multiple machines under real-time schedulingProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301420(622-631)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301250.301420

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Note-Patience is a Virtue in a Simple Model of Repetitively Joining a Queue

QBD approximations of a call center queueing model with general patience distribution

A Unified Approach to Diffusion Analysis of Queues with General Patience-Time Distributions