Publications

Auxiliary Storage

  1. Coffman, E. G., Jr. and Hofri, M., ``Queueing Models of Secondary Storage Devices,'' Queueing Sys. Th. and Applic., 2(1986), 129-168.

  2. Coffman, E. G., Jr., and Hofri, M., ``On The Expected Performance of Scanning Disks,'' Proc., 3rd Int. Symp. on Performance Evaluation, 1977 (PE'77). (Expanded version below)

  3. Coffman, E. G., Jr., and Hofri, M., ``On The Expected Performance of Scanning Disks,'' SIAM J. Comput., 11 (1982), 60-70.

  4. Coffman, E. G., Jr., and Hofri, M., ``A Class of FIFO Queues Arising in Computer Systems,'' Oper. Res., 26 (1978), 864-880.

  5. Coffman, E. G., Jr., Leung, J. Y-T., and Johnson, D. B., ``An Efficient Algorithm for Allocating Paged, Drum-Like Storage,'' Proc. Johns Hopkins Conf. on Inf. Systems and Sciences, April 1977. (Expanded version below)

  6. Coffman, E. G., Jr., Leung, J. Y-T., and Johnson, D. B., ``An Efficient Algorithm for Allocating Paged, Drum-Like Storage,'' BIT, 18 (1978), 52-66.

  7. Cody, R.A., and Coffman, E.G.,Jr., ``Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices,'' Proc. 8-th Princeton Conf. on Inf. Sci. & Sys., March 1974. (Expanded version below)

  8. Cody, R.A., and Coffman, E.G.,Jr., ``Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices,'' J. Assoc. Comp. Mach., 23 (1976), 103-115.

  9. Coffman, E.G., Jr., and Trumbull, C.J.M., ``A Comparison of Two Disk Scanning Policies,'' Inf. Proc. Letters, 2 (1973), 15-17.

  10. Coffman, E.G., Jr., Klimko, L.A., and Ryan, B., ``Analysis of Scanning Policies for Reducing Disk Seek Times,'' SIAM J. Comput., 1 (1972), 269-279.

  11. Coffman, E.\ G., Jr., ``Analysis of a Drum Input/Output Queue under Scheduled Usage in a paged Computer System,'' J. Assoc. Comp. Mach., 16 (1969), 73-90. Corrigendum: 16 (1969), 646.

Bin Packing: Combinatorial Analysis

  1. Coffman, E. G., Jr., J. Csirik, ``A Classification Scheme for Bin Packing Theory,'' Acta Cybernetica , Vol. 18, pp. 47-60, 2007.
    File:  pdf

  2. Coffman, E. G., Jr. and G. S. Lueker, ``Approximation Algorithms for Extensible Bin Packing,'' Proceedings, 12-th Annual ACM-SIAM Symp. on Discrete Alg. (SODA'01), Washington D.C., 2001. (Expanded version below)

  3. Coffman, E. G., Jr. and G. S. Lueker, ``Approximation Algorithms for Extensible Bin Packing'' J. of Scheduling 9(2006), 77-84.
    File:  postscript

  4. Coffman, E. G., Jr., Garey, M. R. and Johnson, D. S., ``Bin-Packing with Divisible Item Sizes,'' J. Complexity 3(1987), 406-428.

  5. Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., ``Dynamic bin-packing,'' SIAM J. Comput., 12 (1983), 227-258. (One of SIAM's Best Paper nominations for 1983.)

  6. Coffman, E. G., Jr., ``An Introduction to Proof Techniques for Packing and Sequencing Algorithms,'' in Deterministic and Stochastic Scheduling, M. A. H. Dempster, et. al. (eds.), Reidel, Amsterdam (1982), 245-270.

  7. Baker, B. S. and Coffman, E. G., Jr., ``A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing,'' SIAM J. Alg. Disc. Math. 2 (1981), 147-152.

  8. Coffman, E. G., Jr., and Leung, J. Y-T., ``Bin Packing with a Fixed Number of Bins: An Iterative Algorithm,'' Proc., 18-th Symp. on the Foundations of Computer Science (FOCS'77), 1977, 214-221. (Expanded version below)

  9. Coffman, E. G., Jr., and Leung, J. Y-T., ``Bin Packing with a Fixed Number of Bins: An Iterative Algorithm,'' SIAM J. Comput., 8 (1979), 202-217.

  10. Coffman, E. G., Jr., Leung, J. Y-T., and Ting, D., ``Bin Packing: Maximizing the Number of Pieces Packed,'' Acta Informatica, 9 (1978), 263-271.

  11. Cody, R. A., Coffman, E. G., Jr., and Johnson, D. B., ``Analysis of a Bin-Packing Algorithm for Reducing Access Times on Drum-Like Storage Devices,'' Foundations of Control Engineering, Poznan, Poland, 2 (1977), 119-130.

  12. Coffman, E.G., Jr., and Leung, J. Y-T., and Ting, D. ``Bin-Packing Problems and Their Applications in Storage and Processor Allocation,'' in Computer Performance, Chandy, K.M. and Reiser, M. (eds.), North Holland (1977), 327-339.

Bin Packing: Average Case Analysis

  1. Coffman, E.G., Jr., J. Csirik, L. Ronyai, and A. Zsban , `` Random-Order Bin Packing,'' Discrete Applied Math., 156(14), 2810-2816(2008). File:  pdf

  2. Coffman, E.G., Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, ``Perfect Packing Theorems and the Average-Case Behavior of Optimal and On-line Packings,'' SIAM Rev. 44 (2002), 384-402.

  3. Coffman, E.G., Jr., Johnson, D.S., McGeoch, L.A., and Weber, R.R., ``Average-Case Analysis of FFD and BFD Packing under Discrete Uniform Distributions,'' Bell Labs Tech. Rep., 1998

  4. Asgeirsson, E., Ayesta, U., Coffman, E., Etra, J., Momcilovic, P., Phillips, D., Vokhshoori, V., Wang, Z., and Wolfe, J., ``Closed On-Line Bin Packing,'' Acta Cybernetica , 15 (2002), 361-367 .

  5. Coffman, E.G., Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, ``Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings,'' SIAM J. Discrete Math. 13 (2000), 384-402.
    File:  pdf postscript

  6. Coffman, E.G.,Jr. and Stolyar, A.L., ``Fluid Limits, Bin Packing and Stochastic Analysis of Algorithms'' Proc. 10-th Ann. ACM/SIAM Symp. Disc. Algs. (SODA'99), Baltimore, Jan. 1999, S787-S788.
    File:  pdf postscript

  7. E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and R. R. Weber, ``Bin Packing with Discrete Item Sizes, Part II: Tight Bounds on First Fit,'' Random Structures and Algorithms 10 (1997), 69-101.
    File:  pdf postscript

  8. Coffman, E.G., Jr., Johnson, D.S., Shor, P.W., and Weber, R.R., ``Markov Chains, Computer Proofs, and Best-Fit Bin Packing,'' Proc. ACM Symp. Th. Comput. (STOC'93), 1993, 412-421.

  9. Coffman, E. G. Jr., Courcoubetis, C. A., Garey, M. R., Johnson, D. S., McGeoch, L. A., Shor, P. W., Weber, R.R., and Yannakakis, M., ``Average-Case Performance of One-Dimensional Bin Packing Algorithms under Discrete Uniform Distributions,'' Proc. ACM Symp. Th. Comput. (STOC'91), ACM Press, 1991, 230-240.

  10. Coffman, E. G., Jr., So, K., Hofri, M., and Yao, A. C., ``A Stochastic Model of Bin-Packing,'' Information and Control, 44 (1980), 105-115.

Bin Packing: Higher Dimensions

  1. Coffman, E. G., Jr., Downey, P. J., and Winkler, P., ``Packing Rectangles in a Strip,'' Acta Informatica, 38 (2002), 673-693.
    File:  postscript

  2. Coffman, E. G., Jr., G. S. Lueker, J. Spencer, and P. Winkler, ``Average-Case Analysis of Rectangle Packings,'' In LATIN 2000: Theoretical Informatics, G. H. Gonnet, D. Penario, and A. Viola, eds., 292--297.

  3. Coffman, E. G., Jr., G. S. Lueker, J. Spencer, and P. Winkler, ``Packing Random Rectangles,'' Prob. Th. Related Fields, 4 (2001), 585-599.
    File:  postscript

  4. Coffman, E.G.,Jr., Flajolet, Ph., Flatto, L., and Hofri, M., ``The Maximum of a Random Walk and Its Application to Rectangle Packing'' Prob. Eng. Inf. Sci., 12 (1998), 373-386.
    File:  pdf postscript

  5. Coffman, E. G., Jr., and Shor, P. W., ``Packings in Two Dimensions: Asymptotic Average Case Analysis of Algorithms,'' Algorithmica, 9 (1993), 253-277.

  6. Coffman, E. G., Jr., and Lagarias, J. C., ``Algorithms for Square Packing: A Probabilistic Analysis'', SIAM J. Comput., 18(1989), 166-185.

  7. Baker, B. S., Calderbank, A. R., Coffman, E. G., Jr., and Lagarias, J. C., ``Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle,'' SIAM J. Alg. Disc. Meth., 4 (1983), 383-397.

  8. Baker, B. S., and Coffman, E. G., Jr., ``A Two-Dimensional Bin-Packing Model of Preemptive FIFO Storage Allocation,'' J. Algorithms, 3 (1982), 303-316.

  9. Coffman, E. G., Jr., Garey, M. R., Johnson, D. S., and Tarjan, R. E., ``Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms,'' SIAM J. Comput., 9 (1980), 808-826.

  10. Baker, B. S., Coffman, E. G., Jr., and Rivest, R. L., ``Orthogonal Packings in Two Dimensions,'' Proc. Allerton Conf. on System and Circuit Theory, Oct.1978. (Expanded version below)

  11. Baker, B. S., Coffman, E. G., Jr., and Rivest, R. L., ``Orthogonal Packings in Two Dimensions,'' SIAM J. Comput., 9 (1980), 846-855.

Bin Packing: Surveys and Books

  1. Coffman, E.G., Jr., Csirik, J., Galambos, G., Martello, S., and Vigo, D., ``Bin Packing Approximation Algorithms: Survey and Classification,'' in Handbook of Combinatorial Optimization, 2nd Edition (2013), 455-531, Springer, New York.

  2. Coffman, E. G., Jr., J. Csirik, and J. Leung, ``Variable Sized Bin Packing and Bin Covering,'' Chapter 34, Handbook of Approximation Algorithms and Meta-Heuristics, Teofilo Gonzalez, ed., Francis and Taylor Books (CRC Press), 2006.

  3. Coffman, E. G., Jr., J. Csirik, and J. Leung, ``Variants of Classical One-Dimensional Bin Packing,'' Chapter 33, Handbook of Approximation Algorithms and Meta-Heuristics, Teofilo Gonzalez, ed., Francis and Taylor Books (CRC Press), 2006.

  4. Coffman, E. G., Jr. and J. Csirik, ``Performance Guarantees for One-Dimensional Bin Packing,'' Chapter 32, Handbook of Approximation Algorithms and Meta-Heuristics, Teofilo Gonzalez, ed., Francis and Taylor Books (CRC Press), 2006.

  5. Coffman, E. G., Jr., J. Csirik, and G. Woeginger, ``Bin Packing Theory,'' Handbook of Applied Optimization, P. Pardalos and M. Resende, eds., Oxford University Press, New York, 2002.
    File:  pdf postscript

  6. Coffman, E.G., Jr., Galambos, G., Martello, S., and Vigo, D., ``Bin Packing Approximation Algorithms: Combinatorial Analysis,'' in Handbook of Combinatorial Optimization, D.-Z. Du and P. M. Pardalos, Eds., Kluwer Academic Publishers, 1998.
    File:  pdf postscript

  7. Coffman, E.G., Jr., Garey, M.R., and Johnson, D.S, ``Bin Packing Approximation Algorithms: A Survey`` in Approximation Algorithms for NP-Hard Problems, D. Hochbaum (ed.), PWS Publishing Co. (1996), Boston, MA.
    File:  pdf postscript

  8. Coffman, E. G., Jr., Johnson, D. S., Lueker, G.S., and Shor, P. W., ``Asymptotic Probabilistic Analysis of Packing and Related Partitioning Problems,'' National Acad. Sci. Report, Study Group on Probability and Algorithms, 1992.

  9. Coffman, E. G., Jr., Johnson, D. S., Lueker, G.S., and Shor, P. W., ``Asymptotic Probabilistic Analysis of Packing and Related Partitioning Problems,'' Stat. Sci., 8 (1993), 40-47.
    File:  pdf postscript

  10. Coffman, E. G., Jr., and Lueker, G. S., Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley & Sons, 1991.

  11. Coffman, E. G., Jr. and Shor, P. W., ``Average-Case Analysis of Cutting and Packing in Two Dimensions,'' Eur. J. Oper. Res. 44 (1990), 134-144.

  12. Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., ``Approximation Algorithms for Bin-Packing,'' in Algorithm Design for Computer Systems Design, Ausiello, G., Lucertini, M., and Serafini, P. (eds.), Springer-Verlag (1984), 49-106.

Stochastic Matching

  1. Coffman, E.G., Jr., ``Lectures on Stochastic Matching: Guises and Applications,'' AT&T Bell Labs Tech. Rep., 1995
    File:  pdf postscript

  2. Coffman, E.G., Jr., Gilbert, E.N., and Shor, P.W., ``A Selection-Replacement Process on the Circle,'' Ann. Appl. Prob., 3 (1993), 802-818.

  3. Bramel, J., Coffman, E.G., Jr., Shor, P.W., and Simchi-Levi, D., ``Probabilistic Analysis of Algorithms for the Capacitated Routing Problem with Unsplit Demands,'' Oper. Res., 40 (1992), 1095-1106.

  4. Coffman, E. G., Jr. and Shor, P. W., ``A Simple Proof of the sqrt(n log3/4 n) Up-Right Matching Bound,'' SIAM J. Disc. Math.,Feb., 1991, 48-57

  5. Coffman, E.G., Jr., Shor, P. W., ``An Asymptotic Probabilistic Analysis of Vehicle Routing,'' AT&T Bell Labs Tech. Rep. (1990).
    File:  pdf postscript

Communication Systems

  1. Baryshnikov, Y. M., E. G. Coffman, Jr., and P. Jelenkovic, ``Kelly's LAN Model Revisited," Performance Evaluation Review, 29 (2001), 28--29.
    File:  postscript

  2. Borst, S. C., E. G. Coffman, Jr., E. N. Gilbert, P. Whiting, and P. Winkler, ``Optimal Carrier Sharing in Wireless TDMA," J. Interconnection Networks , 2 (2001), 189--212.

  3. Coffman, E.G.,Jr., Gilbert, E.N., and Kogan, Y. A., ``Redialing Policies: Optimality and Success Probabilities'' Prob. Eng. and Inf. Sci., 13 (1999), 37-53.
    File:  pdf postscript

  4. Borst, S. C., E. G. Coffman, Jr., E. N. Gilbert, P. Whiting, and P. Winkler, ``Time Slot Allocation in Wireless TDMA,'' Chapter 14 in System Performance Evaluation: Methodologies and Applications, E. Gelenbe, ed., CRC Press, 2000.
    File:  pdf postscript

  5. Coffman, E. G., Jr., Gilbert, E. N., and Kogan, Y. A., ``Optimal Redialing Services,'' Proc. 15-th Internat'l Teletraffic Congress,Vol. 2b, 1997, Eds. V. Ramaswami and P. E. Wirth, Elsevier, Amsterdam, 943-952.

  6. Applegate, D., Coffman, E. G., Jr., and Johnson, D. S., ``Dynamic Allocation of Bridge Circuits in Teleconferencing Services,'' Internal memo. AT&T proprietary.

  7. Coffman, E. G., Jr., Halfin, S., Jean-Marie, A. and Robert, P., ``Analysis of a Slotted Communication Channel with Next-Fit Message Assignment,'' IEEE Trans. Inf. Th., 39(1993), 1555--1566.

  8. Coffman, E. G., Jr., Flatto, L., and Gaver, D. P., Jr., ``Height Distributions in a Buffer Model with Locking Protocols,'' Stochastic Models, 7 (1991), 243-260.

  9. Coffman, E. G., Jr., Igelnik, B. M., and Kogan, Y. A., ``Controlled Stochastic Model of a Communication System with Multiple Sources,'' Proc. International Teletraffic Congress, June 1991. (Expanded version below)

  10. Coffman, E. G., Jr., Igelnik, B. M., and Kogan, Y. A., ``Controlled Stochastic Model of a Communication System with Multiple Sources,'' IEEE Trans. Information Th., 37 (1991), 1379-1387.

  11. Coffman, E. G., Jr., Halfin, S., Jean-Marie, A., and Robert, P., ``Stochastic Analysis of a Slotted FIFO Communication Channel: Constant and Uniform Message Lengths,'' Proc. 4-th Internat'l Conf. Data Comm. Sys., Barcelona, 1990.

  12. Coffman, E. G., Jr., Flatto, L. and Gaver, D. P., ``Performance Analysis of a Buffer under Locking Protocols,'' Proc. 4-th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation, University of the Balearic Islands (1988), 213-232.

  13. Coffman, E. G., Jr. and Reiman, M. I. ``Diffusion Approximations for Computer/Communication Systems'', in Mathematical Computer Performance and Reliability, Iazeolla, G., Courtois, P.-J. and Hordijk, A. (eds.), North Holland (1984), 33-53.

Database Performance

  1. Baccelli, F. and Coffman, E. G., Jr., ``A Data Base Replication Analysis Using an M/M/m Queue with Service Interruptions,'' Performance Evaluation Review, 11 (1982), 102-107.

  2. Coffman, E. G., Jr., Gelenbe, E., Pollak, H. O., and Wood, R., ``An Analysis of Parallel-Read, Sequential-Write Systems,'' Performance Evaluation Review, 9 (1980), 209-216.

  3. Coffman, E. G., Jr., Gelenbe, E., Pollak, H. O., and Wood, R., ``An Analysis of Parallel-Read, Sequential-Write Systems,'' Performance Evaluation 1 (1981), 62-69.

  4. Coffman, E. G., Jr., Gelenbe, E., and Plateau, B., ``Optimization of the Number of Copies in a Distributed Data Base,'' IEEE Trans. Soft. Eng., SE-7 (1981), 78-84.

Data Structures and Algorithms

  1. Coffman, E. G., Jr. and P. Jelenkovic, ``Performance of the Move-To-Front Algorithm with Markov Modulated Request Sequences,'' Inf. Proc. Lett., 25 (1999), 109-118.
    File:  pdf postscript

  2. Bruno, J. L., and Coffman, E.G., Jr., ``Nearly Optimal Binary Search Trees,'' Proc. IFIP '71 Congress, North Holland (1972), 99-103.

  3. Coffman, E.G., Jr., and Eve, J., ``File Structures Using Hashing Functions,'' Comm. Assoc. Comp. Mach., 13 (1970), 427-433.

  4. Bruno, J.L., and Coffman, E.G., Jr., ``On File Structuring for Non-Uniform Access Frequencies,'' BIT 10 (1970), 443-456.

  5. Coffman, E. G., Jr., and McKellar, A. C., ``On the Motion of an Unbounded Markov Queue in Random Access Storage,'' IEEE Trans. Comp., C-17 (1968), 600-603.

Dynamic Resource Allocation

  1. Coffman, E. G., Jr., Robert, Ph., Simatos, F., Tarumi, S., and Zussman, G. ``Channel Fragmentation in Dynamic Spectrum Access Systems: A Theoretical Study,'' Proc. ACM SIGMETRICS Conf., pp. 333-344, 2010 (Journal version below).

  2. Coffman, E. G., Jr., Robert, Ph., Simatos, F., Tarumi, S., and Zussman, G. ``Channel Fragmentation in Dynamic Spectrum Access Systems: A Performance Analysis,'' Queueing Systems, Theory and Applications, 2012 (to appear).

  3. Coffman, E. G., Jr., ``Computer Storage Fragmentation: Pioneering Work of Brian Randell,'' Dependable and Historic Computing, LNCS, Vol. 6875, 2011, pp. 174-184.

  4. Coffman, E. G., Jr., Flatto, L., Leighton, F. T., ``First-Fit Allocation of Queues: Tight Asymptotic Bounds on Expected Wasted Space,'' Proc. First Ann. Symp. Disc. Alg. (SODA'90), 1990. (Expanded version below)

  5. Coffman, E. G., Jr., Flatto, L., Leighton, F. T., ``First-Fit Allocation of Queues: Tight Asymptotic Bounds on Expected Wasted Space,'' Stoch. Proc. Applic., 36 (1990), 311-330.

  6. Coffman, E. G., Jr., Leighton, F. T., ``A Provably Efficient Algorithm for Dynamic Storage Allocation,'' Proc. ACM Symp. Th. Comput. (STOC'86), (1986), 77-90. (Expanded version below)

  7. Coffman, E. G., Jr., Leighton, F. T., ``A Provably Efficient Algorithm for Dynamic Storage Allocation,'' J. Comp. Sys. Sci., 8 (1989), 2-35.

  8. Coffman, E. G., Jr., Flatto, L., Knessl, C., Mitrani, I. and Shepp, L. A., ``Stochastic Models of Queue Storage,'' Prob. Eng. and Inf. Sci., 2 (1988), 75-93.

  9. Coffman, E. G., Jr., Kadota, T. T., Leighton, F. T. and Shepp, L. A., ``Stochastic Analysis of Storage Fragmentation,'' Proc. Int. Seminar on Teletraffic Analysis and Computer Performance Evaluation, O. J. Boxma, J. W. Cohen and H. C. Tijms (eds.), North Holland (1986), 275-295.

  10. Coffman, E. G., Jr., Kadota, T. T., and Shepp, L. A., ``A Stochastic Model of Fragmentation in Dynamic Storage Allocation,'' SIAM J. Comput., 14 (1985), 416-425

  11. Coffman, E. G., Jr., and Mitrani, I., ``Storage of the Single Server Queue,'' in Queueing Theory and Its Applications, Boxma, O. J. and Syski, R. (eds.), CWI Monographs, North Holland (1988), 193-205.)

  12. Coffman, E. G., Jr., Kadota, T. T., and Shepp, L. A., ``On the Asymptotic Optimality of First-Fit Storage Allocation,'' IEEE Trans. Soft. Eng., SE-11 (1985), 235-239.

  13. Baker, B. S., Coffman, E. G., Jr., and Willard, D. E., ``Algorithms for Resolving Conflicts in Dynamic Storage Allocation,'' J. Assoc. Comp. Mach., 2 (1985), 327-343.

  14. Baker, B. S. and Coffman, E. G., Jr., ``Insertion and Compaction Algorithms in Sequentially Allocated Storage,'' SIAM J. Comput., 13 (1984), 600-609.

  15. Coffman, E. G., Jr., and Gilbert, E. N., ``Dynamic Storage Allocation in Two or More Dimensions,'' Information and Control, 61 (1984), 1-14.

  16. Coffman, E. G., Jr., ``An Introduction to Combinatorial Models of Dynamic Storage Allocation,'' SIAM Review, 25 (1983), 311-325.

Networks: General

  1. Baryshnikov, Y., Coffman, E.G., Jr., Feng, J. Momcilovic, P., An Analysis of AIMD Congestion Control, , Proceedings, 7-th INFORMS Telecommunications Conf., Deerfield Beach, 2004.
    File:  pdf

  2. Baryshnikov, Y., Coffman, E.G., Jr., Feng, J. Misra, V., ``Free-Drop TCP,'' Perf. Eval. Rev., 34 (2006), 33--35.
    File:  pdf

  3. Berger, A.W., Coffman, E.G., Jr., Kogan, Y, Network Engineering of Elastic Data Traffic via Tandem Queueing Network Models, , Proceedings, Third INFORMS Telecommunications Conf., Boca Raton, 2000.
    File:  boca.ps

  4. Coffman, E. G., Jr., Feldmann, A., Kahale, N., and Poonen, B., ``Computing Call Admission Capacities in Linear Networks,'' Prob. Eng. Inf. Sci., 13 (1999), 387-406.
    File:  pdf postscript

  5. Andrew, L. L. H., Baryshnikov, Y., Coffman, E. G., Jr., Hanly, S. V., and White, J., `` An Asymptotically Optimal Greedy Algorithm for Large Optical Burst Switching Systems,'' Perf. Eval. Rev., 31 (2003).
    File:  pdf

  6. Kwak, K. J. and Coffman, E. G., Jr., ``Retransmission in OBS Networks with Fiber Delay Lines," Proc., 4-th Int. Conf. Broadband Comm., Nets, Sys.," (BroadNets) Raleigh, NC, Sept. 2007.

  7. Coffman, E.G., Jr. and Stolyar, A.L., ``Bandwidth Packing'' Algorithmica, 29 (2001), 70-88.
    File:  pdf postscript

  8. Coffman, E.G., Jr., Robert, Ph., and Stolyar, A.J., ``The Interval Packing Process of Linear Networks'' Perf. Eval. Rev., 27, Dec. 1999.
    File:  pdf postscript

  9. Coffman, E.G., Jr., Kahale, N., and Leighton, F.T., ``Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times,'' SIAM J. Comput., 27 (1998), 1221-1236.
    File:  pdf postscript

  10. Coffman, E.G., Jr., Flatto, L., Gilbert, E.N., and Greenberg, A.G., ``An Approximate Model of Processor Communication Rings under Heavy Traffic,`` Inf. Proc. Lett., 64 (1997), 61-67.
    File:  pdf postscript

  11. Bayer, N., Coffman, E.G., Jr., and Kogan, Y.A., ``An Asymptotic Analysis of Closed Queueing Networks with Branching Populations'' Tech. Rep., AT&T Bell Laboratories, 1996.

  12. Coffman, E.G., Jr., Gilbert, E. N., Greenberg, A. G., Leighton, F. T., Robert, Ph., and Stolyar, A., ``Queues Served by a Rotating Ring,'' Stochastic Models, 11 (1995), 371--394.
    File:  pdf postscript

  13. Coffman, E.G., Jr., Mallows, C.L., and Poonen, B., ``Parking Arcs on the Circle with Applications to One-Dimensional Communication Networks,'' Ann. Appl. Prob., 4 (1994), 1098--1111.

  14. Chung, F. R. K., Coffman, E. G., Jr., Reiman, M. L., and Simon, B., ``The Forwarding Index of Communication Networks,'' IEEE Trans. on Information Th., IT-33 (1987), 224-232.

  15. Coffman, E. G., Jr., Garey, M. R., Johnson, D. S., and LaPaugh, A. S., ``Scheduling File Transfers,'' Proc. 2nd Ann. ACM Symp. Principles of Distributed Computing, 1983, 254-266. (Expanded version below)

  16. Coffman, E. G., Jr., Garey, M. R., Johnson, D. S., and LaPaugh, A. S., ``Scheduling File Transfers,'' SIAM J. Comput., 14 (1985), 744-780.

Networks: Sensor Systems

  1. Baryshnikov, Y., Coffman, E. G., and Kwak, K. J., ``High Performance Sleep-Wake Sensor Systems Based on Cyclic Cellular Automata,'' Proc. ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN'08)

  2. Kwak, K. J., Baryshnikov, Y., and Coffman, E. G., ``Cyclic Cellular Automata: A Tool for Self-Organizing Sleep Scheduling for Sensor Networks,'' Demo paper in: Proc. ACM/IEEE Int. Conf. Inf. Proc. in Sensor Nets (IPSN 2008)

  3. Baryshnikov, Y., Coffman, E. G., Kwak, K. J., and Moran, W., ``Stochastic Counting in Sensor Networks: or, Noise is Good,'' Proc. ACM/IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2008. (Expanded version below)

  4. Baryshnikov, Y., Coffman, E. G., Kwak, K. J., and Moran, W., ``Stochastic Counting in Sensor Networks (Noise Helps),'' Ad Hoc Networks (to appear).

  5. Baryshnikov, Y., Coffman, E. G., and Kwak, K. J., ``Cauchy Localization: A Distributed Computation on WSNs,'' Perf. Eval. Rev., Sept. 2011, 59-61, Proc. of 29th IFIP Performance Conf., 2011 .

  6. Kwak, Kyung Joon, Baryshnikov, Yuliy, and Coffman, E. G., Jr., ``Self-Organizing Sleep-Wake Sensor Systems,'' 2nd International IEEE Conference on Self-Adaptive and Self-Organizing Systems, (SASO'08), 393-402.

Interval Problems

  1. Baryshnikov, Y., Coffman, E.G., Jr., and Jelenkovic, P., ``Space Filling and Depletion'' , J. Appl. Prob., 41 (2004), 691-702.
    File:  postscript

  2. Coffman, E.G., Jr., Flatto, L., Jelenkovic, P., ``Interval Packing: The Vacant-Interval Distribution'' Ann. Appl. Prob., 10 (2000), 240-257.
    File:  pdf postscript

  3. Coffman, E.G., Jr., Flatto, L., Jelenkovic, P., and Poonen, B., ``Packing Random Intervals On-Line'' Algorithmica 22 (1998), 448-476.
    File:  postscript

  4. Coffman, E.G., Jr., Flatto, L., and Jelenkovic, P., ``A Central Limit Theorem for Stochastic Interval Packing,'' Tech. Rep., Bell Labs, 1997.
    File:  pdf postscript

  5. Coffman, E.G., Jr., Poonen, B., and Winkler, P., ``Packing Random Intervals,'' Probability Theory and Related Fields, 102 (1995), 105--121.
    File:  pdf postscript

  6. Coffman, E. G., Jr., Fayolle, G., Jacquet, P., and Robert, P., ``Largest-First Sequential Selection with a Sum Constraint,'' Op. Res. Letters, 9 (1990), 141-146.

  7. Coffman, E. G., Jr., Flatto, L. and Weber, R. R., ``Optimal Selection of Stochastic Intervals under a Sum Constraint,'' Adv. Appl. Prob., 19 (1987), 454-473.

Moving--Server Problems

  1. Calderbank, A. R., Coffman, E. G., Jr., and Flatto, L., ``A Note Extending the Analysis of Two-Head Disk Systems to More Realistic Seek-Time Characteristics,'' IEEE Trans. Comp., 38 (1989), 1584-1586.

  2. Calderbank, A. R., Coffman, E. G., Jr. and Flatto, L., ``Optimal Directory Placement on Disk Storage Devices,'' J. Assoc. Comp. Mach., 35 (1988), 433-446.

  3. Calderbank, A. R., Coffman, E. G., Jr., and Flatto, L., ``Sequencing Two Servers on the Sphere,'' Stochastic Models, 1 (1985), 17-28.

  4. Calderbank, A. R., Coffman, E. G., Jr., and Flatto, L., ``Sequencing Problems in Two-Server Systems,'' Math. Oper. Res., 10 (1985), 595-598.

  5. Calderbank, A. R., Coffman, E. G., Jr., and Flatto, L. ``Optimum Head Separation in a Disk System with Two Read/Write Heads,'' J. Assoc. Comp. Mach., 31 (1984), 826-838.

Computer Systems

  1. Coffman, E. G., Jr., and Sethi, R., ``Instruction Sets for Evaluating Arithmetic Expressions,'' J. Assoc. Comp. Mach., 30 (1983), 457-478.

  2. Coffman, E. G., Jr. and So, K., ``On the Comparison Between Single and Multiple Processor Systems,'' Proc. 17th IEEE/ACM Symp. on Computer Architecture, (1980), 72-79.

  3. Coffman, E. G., Jr., Ryan, T. A., and Ryan, B., ``Markov Models of Parallelism in Loading and Execution of a Single Process,'' Computer Architectures and Networks, Gelenbe, E. and Mahl, R. (eds.), North Holland (1974), 375-387.

  4. Steven M. Nowick, E. G. Coffman, Peggy B. McGee, ``Efficient performance analysis of asynchronous systems based on periodicity," Proceedings, Third IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'05), 2005, pp. 225--230.

  5. Coffman, E.G., Jr., ``A Formal Microprogram Model of Parallelism and Register-Sharing,'' Computers and Automata, Symp. Proc. Vol.XXI, Polytechnic Press, Polytechnic Institute of Brooklyn (1971), 215-223.

  6. Coffman, E.G., Jr., ``Formal Models of Computer Systems Design,'' Proc. 2nd Int. Seminar on Computer Science, Sept. 1969. Computing Laboratory, University of Newcastle upon Tyne, England.

  7. Coffman, E.G., Jr., and Muntz, R.R., ``Models of Resource Allocation Using Pure Time-Sharing Disciplines,'' Proc. 24th ACM Nat. Conf., (1969), 217-228.

  8. Coffman, E. G., Jr., and Kleinrock, L., ``Computer Scheduling Methods and Their Countermeasures,'' AFIPS Conf. Proc., 32 (1968 SJCC), 11-21.

Operating Systems

  1. Coffman, E.G., Jr., Elphick, M., and Shoshani, A., ``System Deadlocks,'' Computing Surveys, 2 (1971), 67-78.

  2. Coffman, E.G., Jr., Elphick, M., and Shoshani, A., ``System Deadlocks,'' Distributed Computing: Concepts and Implementations, McEntire, P.L., O'Reilly, J.G. and Larsen, R.E. (eds.), IEEE Press, 1984.

  3. Coffman, E.G., Jr., and Denning, P.J., Operating Systems Theory, Prentice-Hall, 1973.

  4. Coffman, E.G., Jr., ``Deadlocks in Computer Systems,'' in Infotech State-of-the-Art Reports, Infotech Ltd., England 1973.

  5. Bruno, J.L., Coffman, E.G., Jr., and Hosken, W., ``Consistency of Synchronization Nets Using P and V Operations,'' Proc. 13-th Symp. Switching and Automata Theory (SWAT'72), (1972), 71-76.

  6. Coffman, E.G., Jr., and Shoshani, A., ``Sequencing Tasks in Multiprocess Multiple Resource Systems to Avoid Deadlocks,'' Proc. 10-th Symp. Switching and Automata Theory (SWAT'70), (1970), 225-233.

  7. Coffman, E.G., Jr., and Shoshani, A., ``Detection and Prevention of Deadlocks,'' Proc. Third Annual Princeton Conf. on Inf. Sci. Sys., March 1970.

  8. Coffman, E. G., Jr. Schwartz, J. I., and Weissman, C., ``Potentials in Large-Scale Time-Sharing Systems,'' Proc. 2-nd Congress, Information Systems and Sciences, Spartan Books, Baltimore, 1964.

  9. Coffman, E. G., Jr. Schwartz, J. I., and Weissman, C., ``A General Purpose Time-Sharing System,'' AFIPS Conf. Proc., (1964 SJCC), Sparton Books, Baltimore, 347-411. (Best Paper award). pdf

Polling

  1. Coffman, E.G., Jr., Puhalskii, A.A., and Reiman, M.I., ``Polling Systems in Heavy Traffic: A Bessel Process Limit'' Math. Oper. Res., 23 (1998), 257-304 (award winning paper).
    File:  pdf postscript

  2. Coffman, E.G., Jr., Pukhalskii, A.A., and Reiman, M.I., ``Polling Systems with Zero Switchover Times: A Heavy-Traffic Averaging Principle,'' Ann. Appl. Prob. 23 (1995), 681-219.
    File:  pdf postscript

  3. Coffman, E.G., Jr. and Stolyar, A., ``Continuous Polling on Graphs,'' Prob. Eng. Inf. Sci., 7 (1993), 209-226.

  4. Coffman, E. G., Jr., Gilbert, E. N., ``Polling and Greedy Servers on a Line,'' Queueing Sys., Th. and Applic., 2 1987), 115-145.

  5. Coffman, E. G., Jr., and Gilbert, E. N., ``A Continuous Polling System with Constant Service Times,'' IEEE Trans. on Information Th., IT-32 (1986), 584-591.

Fault Tolerance

  1. Bruno, J.L., Coffman, E.G.,Jr., Lagarias, J.C., Richardson, T.J., and Shor, P.W., ``Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems'' Math. Oper. Res. 24 (1999), 362-382.
    File:  pdf postscript

  2. Bruno, J. and Coffman, E.G., Jr., ``Optimal Fault Tolerant Computing on Two Processors,'' . Acta Informatica, 34 (1997), 881-904.
    File:  pdf postscript

  3. Coffman, E.G.,Jr., Flatto, L., and Kreinin, A., ``Scheduling Saves in Fault Tolerant Computations,'' Acta Informatica, 30 (1993), 409-423.
    File:  pdf postscript

  4. Coffman, E.G., Jr., Flatto, L., and Wright, P.E., ``A Stochastic Checkpoint Optimization Problem,'' SIAM J. Comput., 22 (1993), 650-659.
    File:  pdf postscript

  5. Boguslavsky, L. B., Coffman, E. G., Jr., Gilbert, E. N., and Kreinin, A. Y., ``Scheduling Checks and Saves,'' ORSA J. Comput., 4 (1992), 60-69.

  6. Boguslavsky, L.B., Coffman, E.G.,Jr., and Kreinin, A.Y., ``Optimal Strategies for Scheduling Tests and Saves,'' Proc. 13-th Ann. Internat. Conf. Fault-Tolerant Systems and Diagnostics, Varna, Bulgaria, June 1990.

  7. Coffman, E. G., Jr., and Gilbert, E. N., ``Optimal Strategies for Scheduling Checkpoints and Preventive Maintenance,'' IEEE Trans. Reliability, 39 (1990), 9-18.

Queueing Systems

  1. Coffman, E.G., Jr. and Wright, P.E., ``Load Balancing on Two Identical Facilities,'' Tech. Rep. Bell Labs, 1990.

  2. Coffman, E.G., Jr., Pukhalskii, A.A., Reiman, M.I., and Wright, P.E., ``Asymptotics of Finite Processor Shared Queues with Reneging,'' Performance Evaluation, 19 (1994), 25-46.

  3. Browne, S., Coffman, E.G.,Jr., Gilbert, E.N., and Wright, P.E., ``Gated, Exhaustive, Parallel Service -- The Uniform Case,'' SIAM J. Appl. Math., 52 (1992), 1751-1762.
    File:  pdf postscript

  4. Browne, S., Coffman, E. G., Jr., Gilbert, E. N., and Wright, P. E., ``Gated, Exhaustive, Parallel Service,'' Prob. Eng. Inf. Sci., 6 (1992), 217-239.

  5. Coffman, E. G., Jr. and E. N. Gilbert, ``Service with a Queue and a Cart,'' Manag. Sci., 38 (1992), 867-883.

  6. Baccelli, F., Coffman, E. G., Jr., and Gilbert, E. N., ``Tandem Conveyor Queues,'' Prob. Eng. Inf. Sci. 3 (1989), 517-536.

  7. Coffman, E. G., Jr., Gelenbe, E. and Gilbert, E. N., ``Analysis of a Conveyor Queue in a Flexible Manufacturing System,'' Performance Evaluation Review, 14 (1986), 204-223.

  8. Coffman, E. G., Jr., Gelenbe, E. and Gilbert, E. N., ``Analysis of a Conveyor Queue in a Flexible Manufacturing System,'' Eur. J. Oper. Res., 35 (1988), 382-392.

  9. Coffman, E. G., Jr., Fayolle, G. and Mitrani, I., ``Two Queues with Alternating Service,'' Performance `87, North Holland (1987), 227-239.

  10. Coffman, E. G., Jr., Fayolle, G. and Mitrani, I., ``Sojourn Times in a Tandem Queue with Overtaking: Reduction to a Boundary Value Problem,'' Stochastic Models, 2 (1986), 43-65.

  11. Coffman, E. G., Jr. and Mitrani, I., ``A Characterization of Waiting Times Realizable by Single Server Queues,'' Oper. Res., 28 (1980), 810-821.

  12. Coffman, E.G., Jr., and Mitrani, I., ``Selecting a Scheduling Rule to Meet Pre-Specified Response-Time Demands,'' Operating Systems Review, 9 (1975), 187-191.

  13. Coffman, E.G., Jr., and Michel, J., ``Synthesis of a Feedback Queueing Discipline for Computer Operation,'' Proc. 7th Annual Princeton Conference on Information Sciences and Systems, March 1973. (Expanded version below)

  14. Coffman, E.G., Jr., and Michel, J., ``Synthesis of a Feedback Queueing Discipline for Computer Operation,'' J. Assoc. Comp. Mach., 21 (1974), 329-339.

  15. Coffman, E.G., Jr., Muntz, R.R., and Trotter, H., ``Waiting Time Distributions for Processor-Sharing Systems,'' J. Assoc. Comp. Mach., 17 (1970), 123-130.

  16. Coffman, E. G., Jr., ``Markov Chain Analysis of Multiprogrammed Computer Systems,'' Naval Res. Log. Quart., 16 (1969), 175-197.

  17. Coffman, E. G., Jr., ``On State-Dependent Time Allocation Procedures for Time-Sharing Systems,'' Proc. Purdue Centennial Symposium on Information Processing, Purdue University, April 1969.

  18. Coffman, E.G., Jr., ``On the Trade-Off Between Response and Preemption Costs in a Foreground-Background Computer Service Discipline,'' IEEE Trans. Comp., C-18 (1969), 942-947.

  19. Coffman, E. G., Jr., ``Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping,'' J. Assoc. Comp. Mach., 15 (1968), 341-353.

  20. Coffman, E. G., Jr., ``An Analysis of Computer Operations under Running-Time Priority Disciplines,'' in Interactive Systems for Experimental and Applied Mathematics, Klerer, M. and Reinfelds, J. (eds.), Academic Press (1968), 257-270.

  21. Coffman, E. G., Jr., and Kleinrock, L., ``Feedback Queueing Models for Time-Shared Systems,'' Proc. Fifth International Teletraffic Congress, 1967. (Expanded version below)

  22. Coffman, E. G., Jr., and Kleinrock, L., ``Feedback Queueing Models for Time-Shared Systems,'' J. Assoc. Comp. Mach., 15 (1968), 549-576.

  23. Coffman, E. G., Jr., ``Bounds on Parallel-Processing of Queues with Multiple Phase Jobs,'' Naval Res. Log. Quart., 14 (1967), 345-366.

  24. Coffman, E. G., Jr., and Kleinrock, L., ``Distribution of Attained Service in Time-Sharing Systems,'' J. Comp. Sys. Sci., 1 (1967), 287-298.

  25. Coffman, E. G., Jr. and Wood, R. C., ``Interarrival Statistics for Time Sharing Systems,'' Comm. Assoc. Comp. Mach., 14 (1966), 500-503.

  26. Coffman, E. G. Jr., ``The Study of Multiprogramming Systems,'' Datamation, 1966.

  27. Coffman, E. G., Jr. and Krishnamoorthi, B., ``Preliminary Analyses of Time-Shared Computer Operation,'' Tech. Rep. SP-1719, System Development Corp.,Aug. 1964.

Reservation Systems

  1. Baryshnikov, Y., Coffman, E. G., Jr., and Jelenkovic, P., ``A Limit Law for Reservation Systems,'' Bell Labs Tech. Rep., 1999.

  2. Coffman, E. G., Jr. and Jelenkovic, P., ``Threshold Interval Packing and Reservation Algorithms,'' Performance Evaluation Review. 28 (2001), 9--11.

  3. Coffman, E.G.,Jr., Jelenkovic, P. and Poonen, B., ``Reservation Probabilities,'' Advances in Performance Analysis, 2 (1999), 129--158.
    File:  pdf postscript

Computational Geometry

  1. Coffman, E. G., Jr. and Gilbert, E. N., ``Paths Through a Maze of Rectangles,'' Networks, 22 (1992), 349-367.

Storage Systems: General

  1. Coffman, E. G., Jr., Puhalsky, A. A., and Reiman, M. I., ``Storage Limited Queues in Heavy Traffic,'' Prob. Eng. Inf. Sci., 5 (1991), 499-522.

  2. Boguslavsky, L., Coffman, E. G., Jr., Greenberg, A. G., and Stolyar, A. L., ``Asymptotic Analysis of Memory Interference in Multiprocessor Systems,'' Tech. Rep., Bell Labs, 1991.

  3. Coffman, E. G., Jr., and Reiman, M. I. ``Diffusion Approximations for Storage Processes in Computer Systems,'' Proc. SIGMETRICS Conf., 1983. In Perf. Eval. Rev., Special Issue, 1983, 93-117 (best paper nomination).

  4. Coffman, E. G., Jr., Leung, J. Y-T., and Slutz, D. ``On the Optimality of Fast Heuristics for Scheduling and Storage Allocation Problems,'' Foundations of Control Engineering, Poznan, Poland, 3 (1978).

  5. Coffman, E.G., Jr., and Ryan, T.A., ``A Problem in Multiprogrammed Storage Allocation,'' IEEE Trans. on Comp., C-23 (1974), 1116-1122.

  6. Coffman, E.G., Jr., and Ryan, T.A., ``A Study of Storage Partitioning Using a Mathematical Model of Locality,'' Proc. 3rd ACM Symp. on Operating Systems, Oct. 1971. (Expanded version below)

  7. Coffman, E.G., Jr., and Ryan, T.A., ``A Study of Storage Partitioning Using a Mathematical Model of Locality,'' Comm. Assoc. Comp. Mach., 15 (1972), 185-190.

Storage Systems: Interleaved Systems

  1. Burnett, G.J., and Coffman, E.G., Jr., ``Analysis of Interleaved Memory Systems Using Blockage Buffers,'' Comm. Assoc. Comp. Mach., 18 (1975), 91-95.

  2. Burnett, G.J., and Coffman, E.G., Jr., ``A Combinatorial Problem Related to Interleaved Memories,'' J. Assoc. Comp. Mach., 20 (1973), 39-45.

  3. Burnett, G.J., Coffman, E.G., Jr., and Snowdon, R.A., ``On the Performance of Interleaved Memories with Multiple-Word Bandwidths,'' IEEE Trans. Comp., C-20 (1971), 1570-1573.

  4. Burnett, G.J. and Coffman, E.G., Jr., ``A Study of Interleaved Memory Systems,'' AFIPS Proc., 36 (1970 SJCC), AFIPS Press, Montvale, NJ, 467-474.

Storage Systems: Paging Systems

  1. Coffman, E.G., Jr., and Jones, N., ``Priority Paging Algorithms and the Extension Problem,'' Proc. 12-th Ann. IEEE Symp. Switching and Automata Theory (SWAT'71) (1971), 177-181.

  2. Coffman, E.G., Jr., and B. Randell, ``Performance Predictions for Extended Paged Memories,'' Acta Informatica, 1 (1971), 1-13.

  3. Coffman, E.G., Jr., and McKellar, A.C., ``Organizing Matrices and Matrix Operations for Paged Memory Systems,'' Comm. Assoc. Comp. Mach., 12 (1969), 153-164.

  4. Coffman, E. G., Jr., and Varian, L., ``Further Experimental Data on the Behavior of Programs in a Paged Computer System,'' Proc. First ACM Symp. Operating System Principles, May 1968. (Expanded version below)

  5. Coffman, E. G., Jr., and Varian, L., ``Further Experimental Data on the Behavior of Programs in a Paged Computer System,'' Comm. Assoc. Comp. Mach., 11 (1968), 471-474.

  6. Coffman, E. G., Jr., ``A Probability Model Yielding Performance Bounds for Paging Systems,'' IEEE Trans. on Comp., C-17 (1968), 86-89.

Storage Systems: Surveys and Books

  1. Aven, O. I., Coffman, E. G., Jr. and Kogan, Y. A., Stochastic Models of Computer Storage, Reidel, Amsterdam, 1987.

  2. Coffman, E. G., Jr., ``Recent Progress in the Performance Evaluation of Fundamental Allocation Algorithms,'' Perf. Eval. Rev., 12 (1984), 2-6.

Scheduling Theory: Stochastic

  1. Borst, S., Bruno, J., Coffman, E.G.,Jr., Phillips, S., ``Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines'' Prob. Eng. Inf. Sci., 11 (1997), 95--105.
    File:  pdf postscript

  2. Bruno, J., Coffman, E.G., Jr., and Downey, ``Scheduling Independent Tasks to Minimize the Makespan on Identical Machines,'' Prob. Eng. Inf. Sci., 9 (1995), 447--456.

  3. Coffman, E.G., Jr., Flatto, L., Poonen, B., and Wright, P.E., ``The Processor Minimization Problem with Independent Waiting-Time Constraints,'' Theoretical Comput. Sci., 125 (1994), 3-16.

  4. Coffman, E. G., Jr., Flatto, L., and Wright, P. E., ``Optimal Stochastic Allocation of Machines under Waiting-Time Constraints,'' SIAM J. Comput., 22 (1993), 332-348.

  5. Coffman, E. G., Jr., Flatto, L., and Wright, P. E., ``Stochastic Machine Minimization with Constant Service Times,'' Math. Oper. Res., 18 (1993), 300-316.

  6. Coffman, E. G., Jr. and Liu, Z., ``Optimal Scheduling of Jobs with Out-Forest Precedence Constraints,'' Oper. Res., 40 (1992), Supplement 1, S67-S75.

  7. Coffman, E. G., Jr., Hofri, M., and Weiss, G., ``Scheduling Stochastic Jobs With a Two-Valued Distribution on Two Parallel Processors,'' Prob. Eng. Inf. Sci. 3 (1989), 89-116.

  8. Coffman, E. G., Jr., Flatto, L., Garey, M. R., and Weber, R. R., ``Minimizing Expected Makespans on Uniform Processor Systems,'' Adv. Appl. Prob., 19 (1987), 177-201.

  9. Agrawala, A., Coffman, E. G., Jr., Garey, M. R., and Tripathi, S., ``A Stochastic Optimization Algorithm for Minimizing Expected Flow Times on Uniform Machines,'' IEEE Trans. Comp., C-33 (1984), 351-356.

  10. Bruno, J.L., Coffman, E.G., Jr., and Johnson, D.B., ``On Batch Scheduling of Jobs with Stochastic Service Times and Cost Structures on a Single Server,'' J. Comp. and Sys. Sci., 12 (1976), 319-335.

Scheduling Theory: Combinatorial Analysis

  1. Coffman, E. G., Jr., D. Dereniowski, and W. Kubiak, ``An Efficient Algorithm for Finding Ideal Schedules," Acta Informatica, , 2011.
    File:  pdf

  2. Coffman, E. G., Jr., J. Sethuraman, and V. Timkovsky, ``Ideal Preemptive Schedules on Two Processors," Acta Informatica , 39 (2003), 597-612.
    File:  pdf postscript

  3. Blazewicz, J., Coffman, E. G., Jr., Ecker, K., and Finke, G., Editors: Special Issue of Selected Papers, Dagstuhl Workshop on Scheduling in Computer and Manufacturing Systems, J. Scheduling , 5 (2002).

  4. Coffman, E.G.,Jr. and Even, S., ``A Note on Limited Preemption'' Parallel Processing Letters, 8 (1998), 3-6.
    File:  pdf postscript

  5. Coffman, E. G., Jr., and Garey, M. R., ``Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling,'' Proc. ACM Symp. Th. Comput. (STOC'91), ACM Press, 1991, 241-248. (Expanded version below)

  6. Coffman, E. G., Jr., and Garey, M. R., ``Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling,'' J. Assoc. Comput. Mach., 40 (1993), 991-1018.

  7. Coffman, E. G., Jr., Yannakakis, M., Magazine, M. J., and Santos, C., ``Batch Sizing and Job Sequencing on a Single Machine,'' Ann. Oper. Res., 26 (1990), 135-147.

  8. Coffman, E. G., Jr., Nozari, A. and Yannakakis, M., ``Optimal Scheduling of Products with Two Subassemblies on a Single Machine,'' Oper. Res., 37 (1989), 426-436.

  9. Baker, B.S. and Coffman, E.G., Jr., ``Mutual Exclusion Scheduling,'' Theor. Comput. Sci., 162 (1996), 225--243.
    File:  pdf postscript

  10. Coffman, E. G., Jr., and Yannakakis, M., ``Permuting Elements within Columns to Minimize the Maximum Row Sum of a Matrix,'' Math. Oper. Res., 9 (1984), 384-390.

  11. Coffman, E. G., Jr. and Langston, M. A., ``A Performance Guarantee for Greedy Set Partitioning,'' Acta Informatica, 21 (1984), 409-415.

  12. Coffman, E. G., Jr. Garey, M. R., and Johnson, D. S., ``An Application of Bin-Packing to Multiprocessor Scheduling,'' SIAM J. Comput., 7 (1978), 1-17. (One of SIAM's Best Paper nominations for 1978.)

  13. Coffman, E. G., Jr., and Labetoulle, J., ``Flow-Time Sequencing of Independent Tasks on Multiple Processors,'' Proc. 9th Hawaiian Conference on Information Sciences, Jan. 1976. (Expanded version below)

  14. Coffman, E. G., Jr., and Labetoulle, J., ``Flow-Time Sequencing of Independent Tasks on Multiple Processors,'' INFOR (Can. J. Oper. Res. and Inf. Proc.) 15 (1977), 289-307.

  15. Coffman, E.G., Jr., and Sethi, R., ``A Generalized Bound on LPT Sequencing,'' Computer Performance -- 1976, Chen, P.S. and Franklin, M. (eds.), Assoc. Comput. Mach. (1976), 306-310. (Expanded version below)

  16. Coffman, E.G., Jr., and Sethi, R., ``A Generalized Bound on LPT Sequencing,'' Revue Bleue d'AFCET, (R.A.O. Informatique), 10 (1976), 17-25.

  17. Coffman, E.G., Jr., and Sethi, R., ``Algorithms Minimizing Mean Flow Time: Schedule-Length Properties,'' Acta Informatica, 6 (1976), 1-14.

  18. Bruno, J.L., Coffman, E.G., Jr., and Sethi, R., ``Algorithms for Minimizing Mean Flow Time,'' Proc. IFIPS 74 Congress, North Holland (1974), 504-510.

  19. Coffman, E.G., Jr., ``A Survey of Mathematical Results in Flow-Time Sequencing for Computer Systems,'' Proc. GI73, Springer-Verlag (1973), 25-46.

  20. Bruno, J., Coffman, E.G., Jr., and Sethi, R., ``Algorithms for Reducing Mean Flow Times,'' Proc. ACM Symp. Oper. Sys. Princ. (SOSP'73). In Operating Systems Review, 7 (1973), 102-103. (Expanded version below)

  21. Bruno, J., Coffman, E.G., Jr., and Sethi, R., ``Algorithms for Reducing Mean Flow Times,'' Comm. Assoc. Comp. Mach., 17 (1974), 382-387.

  22. Coffman, E.G., Jr., and Graham, R.L., ``Optimal Scheduling of Two-Processor Systems,'' Proc. 5-th Ann. Princeton Conf. Inf. Sci. Sys.. (Expanded version below)

  23. Coffman, E.G., Jr., and Graham, R.L., ``Optimal Scheduling of Two-Processor Systems,'' Acta Informatica 1 (1972), 200-213.

  24. Coffman, E.G., Jr., and Muntz, R.R., ``Preemptive Scheduling of Real Time Tasks on Multiprocessor Systems,'' J. Assoc. Comp. Mach., 17 (1970), 324-338.

  25. Coffman, E.G., Jr., and Muntz, R.R., ``Preemptive Scheduling of Real Time Tasks on Multiprocessor Systems,'' Hard Real-Time Systems, Stankovic, J.A. and Ramamritham, K., Computer Society press of the IEEE (1988), 190-204.

  26. Coffman, E.G., Jr., and Muntz, R.R., ``Optimal Sequencing of Computation Graphs on Two-Processor Systems,'' Proc. Allerton Conf. on System and Circuit Theory, 1968. (Expanded version below)

  27. Coffman, E.G., Jr., and Muntz, R.R., ``Optimal Sequencing of Computation Graphs on Two-Processor Systems,'' IEEE Trans. Comp., C-18 (1969), 1014-1020.

Scheduling Theory: Probabilistic Analysis

  1. Coffman, E.G., Jr. and Whitt, W., ``Recent Results in the Probabilistic Analysis of Schedule Makespans,'' in Scheduling Theory and Its Applications, Wiley (1995).
    File:  pdf postscript

  2. Coffman, E.G., Jr., Flatto, L. and Whitt, W., ``Stochastic Limit Laws for Schedule Makespans'' Stochastic Models, 12 (1996), 215--243.
    File:  pdf postscript

  3. Coffman, E.G., Jr., Lueker, G.S., and Rinnooy Kan, A.H.G., ``Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics,'' Management Sci.,34 (1988), 266-290.

  4. Coffman, E. G., Jr., Frederickson, G. N., and Lueker, G. S., ``Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors,'' Math. Oper. Res., 9 (1984), 260-266.

  5. Coffman, E. G., Jr., and Gilbert, E. N., ``Expected Relative Performance of List Scheduling Rules,'' Oper. Res., 33 (1985), 548-561.

  6. Coffman, E. G., Jr., Flatto, L. and Lueker, G. S., ``Expected Makespans of Largest-First Sequences,'' Performance `84, Gelenbe, E. (ed.), NorthHolland (1984), 491-506.

Scheduling Theory: Surveys and Books

  1. Chretienne, Ph., Coffman, E.G., Jr., Lenstra, J.K., and Liu, Z. (Editors), Scheduling Theory and Its Applications, Wiley, Chichester, England (1995).

  2. Coffman, E. G., Jr., ``Deterministic Sequencing: Complexity and Optimal Algorithms,'' in Selected Papers on Operating Systems, Arato, M. and Knuth, E. (eds.), KSH Szamki, Budapest (1978), 159-194.

  3. Coffman, E.G., Jr., Computer and Job-Shop Scheduling Theory, John Wiley and Sons, 1975 (editor and co-author). Russian and Polish translations.

  4. Coffman, E.G., Jr., ``Scheduling Theory: Complexity and Optimal Algorithms,'' Proc. Texas Conf. on Computer Science, Nov. 1975.

The Internet

  1. Coffman, E.G., Jr., Constantinides, A., Rubenstein, D., Shepherd, B., and Stavrou, A., ``Content Distribution for Seamless Transmission'', Proc. SIGMETRICS'04 Conf. In Perform. Eval. Rev., 32 (2004), 31--32.
    File:  postscript

  2. Constantinides, A. and Coffman, E., `` Seamless Self-Assembly of Files in Cache Networks at Minimal Storage Cost,'' (2009), submitted for publication.
    File:  postscript

  3. Constantinides, A. and Coffman, E., `` Optimal Seamless Self-Assembly of Files in Linear Networks," Optimization Letters, 1 (2007): 119-128.
    File:  postscript

  4. Baryshnikov, Y., Coffman, E., Jelenkovic, P. Momcilovic, P. and Rubenstein, D., ``Flood Search under the California Split Rule," Oper. Res. Lett., 32 (2004), 199--206.
    File:  postscript

  5. Baryshnikov, Y., Coffman, E., Pierre, G., Rubenstein, D., and Yimwadsana, B., ``Predictability of Web-Server Traffic Congestion,'' Proc., 10-th International Workshop on Web Content Caching and Distribution, 2005.
    File:  postscript

  6. Coffman, E.G.,Jr., Jelenkovic, P., and Momcilovic, P., ``Provably Efficient Stream Merging,'' Proc. 6-th International Workshop on Web Content Caching And Content Distribution , Boston, MA 2001, (Extended version below).
    File:  pdf

  7. Coffman, E.G.,Jr., Jelenkovic, P., and Momcilovic, P., ``The Dyadic Stream Merging Algorithm,'' J. Algorithms, 43(2002), 120--137.

  8. Talim, J., Liu, Z., Nain, P., and Coffman, E.G.,Jr., ``Controlling Robots of Web Search Engines,'' Proc. ACM SIGMETRICS Conference, 2001, 236-244. .
    File:  pdf postscript

  9. Coffman, E. G., Jr., Z. Liu, Ph. Nain, and J. Talim, ``Optimizing the Number of Robots for Web Search Engines,'' Proc. 7-th International Conference on Telecommunication Systems, Nashville, March 1999. (Expanded version below)

  10. Coffman, E. G., Jr., Z. Liu, Ph. Nain, and J. Talim, ``Optimizing the Number of Robots for Web Search Engines,'' Telecomm. Sys. 17 (2001), 245--266.

  11. Coffman, E.G.,Jr., Liu, Z., and Weber, R.R., `Optimal Scheduling of Robots for Web Search Engines,'' J. Scheduling, 1(1998), 15--29.
    File:  pdf postscript

  12. Coffman, E. G., Jr., Z. Ge, V. Misra, and D. Towsley, ``Network Resilience: Exploring Cascading Failures within BGP,'' Proc. 40-th Annual Allerton Conf. on Communications, Computing, and Control (2001).

Nanoscience: Self Assembly

  1. Baryshnikov, Y., Coffman, E.G., Jr., Momcilovic, P., Phase Transitions and Control in Self Assembly , Proceedings, Foundations of Nanoscience: Self-Assembled Architectures and Devices, Snowbird, 2004.
    File:  pdf

  2. Coffman, E. G., Jr., Courtois, P.-J. Gilbert, E. N., and Piret, P., ``A Distributed Clustering Process,'' J. Appl. Prob., 28 (1991), 737-750.

  3. Baryshnikov, Y., Coffman, E.G., Jr., Momcilovic, P., Incremental Self Assembly in the Fluid Limit , Proceedings, 38-th Ann. Conf. Inf. Sys. Sci., Princeton, 2004.
    File:  pdf

  4. Baryshnikov, Y., Coffman, E.G., Jr., Momcilovic, P., DNA-Based Computation Times, , Proc. of the 10-th International Meeting on DNA Computing, Milan, Italy, June 2004..
    File:  pdf

  5. Baryshnikov, Y., Coffman, E.G., Jr., Seeman, N., Yimwadsana, B., Self Correcting Self Assembly: Growth Models and the Hammersley Process, Proc. of the 11-th International Meeting on DNA Computing, London, Ontario, 2005.
    File:  pdf

  6. Baryshnikov, Y., Coffman, E.G., Jr., Yimwadsana, B., Stochastic Yield Analysis of Self-Assembling, Single-Enzyme Reaction Networks, Proc. Foundations of Nanoscience: Self-Assembled Architectures and Devices, Snowbird, 2005.
    File:  ps

  7. Baryshnikov, Y., Coffman, E.G., Jr., Yimwadsana, B., On Creating Shapes in 2D Tile Self-Assembly, Proc. Foundations of Nanoscience: Self-Assembled Architectures and Devices, Snowbird, 2006.
    File:  ps

  8. Baryshnikov, Y., Coffman, E.G., Jr., Yimwadsana, B., Times to Compute Shapes in 2D Self Assembly, Proc. of the 12-th International Meeting on DNA Computing, 2006.
    File:  pdf

  9. Coffman, E. G., Jr., ``Random Phenomena in Algorithmic Self Assembly: Computing Times at Nanoscale,'' Hermis International Journal, 9 (2008), 9-22.

General

  1. Alt, F., Juncosa, M., Gotlieb, C. Miller, R., Coffman, E., Fischer, M., Rosencrantz, D., and Leighton, T. ``Recollections: An Editorial History,'' J. Assoc. Comput. Mach., 50 (2003), 16; 50-th Anniversary Special Issue.

  2. Coffman, E.G., Jr., Principles of Communication Systems: A First Course , First draft, 2003, 86 pages.
    File:  postscript

  3. Coffman, E. G., Matsypura, D., and Timkovsky, V. G., ``Strategy vs. Risk in Margining Portfolios of Options'', 4OR (Quarterly Journal of Operations Research), to appear.

  4. Coffman, Edward G., Jr., Matsypura, Dmytro, and Timkovsky, Vadim G., ``A Computational Study of Margining Portfolios of Options by Two Approaches," in Information Systems, Technology, and Management , Proc. ICISTM, 2010, pp. 325-332.

  5. Coffman, E.G., Jr., Lenstra, J.K., and Rinnooy Kan, Computing (editors), Vol.3, Handbook of Operations Research and Management Science, North Holland, 1992.
TOP /  CONTACT / HOME