|
|
Auxiliary Storage
- Coffman, E. G.,
Jr. and Hofri, M., ``Queueing Models of Secondary Storage Devices,'' Queueing
Sys. Th. and Applic., 2(1986), 129-168.
- Coffman, E. G., Jr.,
and Hofri, M., ``The Expected Performance of Scanning Disks,''
Proc., 3rd Int. Symp. on Performance
Evaluation, 1977 (PE'77). (Expanded version below)
- Coffman, E. G., Jr.,
and Hofri, M., ``On The Expected Performance of Scanning Disks,'' SIAM
J. Comput., 11 (1982), 60-70.
- Coffman, E. G., Jr., and Hofri, M., ``A
Class of FIFO Queues Arising in Computer Systems,'' Oper. Res., 26 (1978), 864-880.
- 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)
- 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.
- 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. Inf. Sci. & Sys.,
March 1974. (Expanded version below)
- 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.
- Coffman, E.G., Jr., and Trumbull,
C.J.M., ``A Comparison of Two Disk Scanning Policies,'' Inf. Proc. Letters, 2 (1973), 15-17.
- 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.
- 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
- Coffman, E. G., Jr., J. Csirik,
``A Classification Scheme for Bin Packing Theory,''
Acta Cybernetica
, Vol. 18, pp. 47-60, 2007.
File: pdf
- 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)
- Coffman, E. G., Jr. and G. S. Lueker,
``Approximation Algorithms for Extensible Bin Packing'' J. of Scheduling 9(2006), 77-84.
File: postscript
- Coffman, E. G., Jr., Garey, M. R. and
Johnson, D. S., ``Bin-Packing with Divisible Item Sizes,''
J. Complexity 3(1987), 406-428.
- 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.)
- 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.
- 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.
- 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)
- 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.
- 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.
- 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.
- 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
- 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
- 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.
- 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
- 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 .
- 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
- 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
- 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
- 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.
- 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.
- 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
- Coffman, E. G., Jr., Downey, P. J., and
Winkler, P., ``Packing Rectangles in a Strip,'' Acta Informatica, 38 (2002), 673-693.
File: postscript
- 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.
- 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
- 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
- Coffman, E. G., Jr., and Shor, P. W.,
``Packings in Two Dimensions: Asymptotic Average Case
Analysis of Algorithms,'' Algorithmica, 9 (1993), 253-277.
- Coffman, E. G., Jr., and Lagarias, J.
C., ``Algorithms for Square Packing: A Probabilistic
Analysis'', SIAM J. Comput., 18(1989), 166-185.
- 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.
- 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.
- 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.
- 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)
- 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
- 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 (to appear 2011).
- 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.
- 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.
- 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.
- 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
- 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
- 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
- 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.
- 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
- Coffman, E. G., Jr., and Lueker, G. S.,
Probabilistic Analysis of Packing
and Partitioning Algorithms, Wiley & Sons, 1991.
- 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.
- 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
- Coffman, E.G., Jr., ``Lectures on
Stochastic Matching: Guises and Applications,'' AT&T Bell Labs Tech. Rep., 1995
File: pdf postscript
- 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.
- 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.
- 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
- 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
- Baryshnikov, Y. M., E. G. Coffman, Jr.,
and P. Jelenkovic, ``Kelly's LAN Model Revisited," Performance Evaluation Review, 29 (2001), 28--29.
File: postscript
- 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.
- 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
- 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
- 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.
- Applegate, D., Coffman, E. G., Jr., and
Johnson, D. S., ``Dynamic Allocation of Bridge Circuits in
Teleconferencing Services,'' Internal memo. AT&T
proprietary.
- 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.
- 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.
- 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)
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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
- 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
- Bruno, J. L., and Coffman, E.G., Jr.,
``Nearly Optimal Binary Search Trees,'' Proc. IFIP '71 Congress, North
Holland (1972), 99-103.
- Coffman, E.G., Jr., and Eve, J., ``File
Structures Using Hashing Functions,'' Comm. Assoc. Comp. Mach., 13 (1970), 427-433.
- Bruno, J.L., and Coffman, E.G., Jr.,
``On File Structuring for Non-Uniform Access Frequencies,''
BIT 10 (1970), 443-456.
- 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
- 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).
- 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).
- Coffman, E. G., Jr.,
``Computer Storage Fragmentation: Pioneering Work of Brian Randell,''
Dependable and Historic Computing, LNCS, Vol. 6875, 2011, pp. 174-184.
- 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)
- 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.
- 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)
- Coffman, E. G., Jr., Leighton, F. T.,
``A Provably Efficient Algorithm for Dynamic Storage
Allocation,'' J. Comp. Sys.
Sci., 8 (1989), 2-35.
- 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.
- 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.
- 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
- 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.)
- 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.
- 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.
- Baker, B. S. and Coffman, E. G., Jr.,
``Insertion and Compaction Algorithms in Sequentially
Allocated Storage,'' SIAM J.
Comput., 13 (1984), 600-609.
- Coffman, E. G., Jr., and Gilbert, E.
N., ``Dynamic Storage Allocation in Two or More
Dimensions,'' Information and
Control, 61 (1984), 1-14.
- Coffman, E. G., Jr., ``An Introduction
to Combinatorial Models of Dynamic Storage Allocation,'' SIAM Review, 25 (1983), 311-325.
Networks: General
- 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
- Baryshnikov, Y., Coffman, E.G., Jr.,
Feng, J. Misra, V., ``Free-Drop TCP,'' Perf. Eval. Rev., 34 (2006), 33--35.
File: pdf
- 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
- 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
- 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
- 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.
- Coffman, E.G., Jr. and Stolyar, A.L.,
``Bandwidth Packing''
Algorithmica, 29 (2001),
70-88.
File: pdf postscript
- 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
- 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
- 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
- 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.
- 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
- 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.
- 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.
- 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)
- 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
-
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)
-
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)
-
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)
-
Baryshnikov, Y., Coffman, E. G., Kwak, K. J., and Moran, W.,
``Stochastic Counting in Sensor Networks (Noise Helps),''
Ad Hoc Networks (to appear).
-
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 .
-
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
- Baryshnikov, Y., Coffman, E.G., Jr., and
Jelenkovic, P., ``Space Filling and Depletion'' , J. Appl. Prob., 41 (2004), 691-702.
File: postscript
- Coffman, E.G., Jr., Flatto, L.,
Jelenkovic, P., ``Interval Packing: The Vacant-Interval
Distribution'' Ann. Appl. Prob.,
10 (2000), 240-257.
File: pdf postscript
- Coffman, E.G., Jr., Flatto, L.,
Jelenkovic, P., and Poonen, B., ``Packing Random Intervals
On-Line'' Algorithmica 22 (1998), 448-476.
File: postscript
- 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
- Coffman, E.G., Jr., Poonen, B., and
Winkler, P., ``Packing Random Intervals,'' Probability Theory and Related
Fields, 102 (1995),
105--121.
File: pdf postscript
- 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.
- 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
- 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.
- 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.
- Calderbank, A. R., Coffman, E. G., Jr.,
and Flatto, L., ``Sequencing Two Servers on the Sphere,'' Stochastic Models, 1 (1985), 17-28.
- Calderbank, A. R., Coffman, E. G., Jr.,
and Flatto, L., ``Sequencing Problems in Two-Server
Systems,'' Math. Oper. Res., 10 (1985), 595-598.
- 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
- Coffman, E. G., Jr., and Sethi, R.,
``Instruction Sets for Evaluating Arithmetic Expressions,''
J. Assoc. Comp. Mach., 30 (1983), 457-478.
- 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.
- 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.
-
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.
- 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.
- 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.
- 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.
- Coffman, E. G., Jr., and Kleinrock, L.,
``Computer Scheduling Methods and Their Countermeasures,''
AFIPS Conf. Proc., 32 (1968 SJCC), 11-21.
Operating Systems
- Coffman, E.G., Jr., Elphick, M., and
Shoshani, A., ``System Deadlocks,'' Computing Surveys, 2 (1971), 67-78.
- 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.
- Coffman, E.G., Jr., and Denning, P.J.,
Operating Systems Theory,
Prentice-Hall, 1973.
- Coffman, E.G., Jr., ``Deadlocks in
Computer Systems,'' in Infotech
State-of-the-Art Reports, Infotech Ltd., England 1973.
- 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.
- 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.
- Coffman, E.G., Jr., and Shoshani, A.,
``Detection and Prevention of Deadlocks,'' Proc. Third Annual Princeton Conf. on
Inf. Sci. Sys., March 1970.
- 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.
- 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
- 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
- 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
- Coffman, E.G., Jr. and Stolyar, A.,
``Continuous Polling on Graphs,'' Prob. Eng. Inf. Sci., 7 (1993), 209-226.
- Coffman, E. G., Jr., Gilbert, E. N.,
``Polling and Greedy Servers on a Line,'' Queueing Sys., Th. and Applic., 2 1987), 115-145.
- 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
- 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
- Bruno, J. and Coffman, E.G., Jr.,
``Optimal Fault Tolerant Computing on Two Processors,'' . Acta Informatica, 34 (1997), 881-904.
File: pdf postscript
- Coffman, E.G.,Jr., Flatto, L., and
Kreinin, A., ``Scheduling Saves in Fault Tolerant
Computations,'' Acta
Informatica, 30 (1993),
409-423.
File: pdf postscript
- 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
- 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.
- 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.
- 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
- Coffman, E.G., Jr. and Wright, P.E.,
``Load Balancing on Two Identical Facilities,'' Tech. Rep. Bell Labs, 1990.
- 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.
- 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
- 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.
- Coffman, E. G., Jr. and E. N. Gilbert,
``Service with a Queue and a Cart,'' Manag. Sci., 38 (1992), 867-883.
- Baccelli, F., Coffman, E. G., Jr., and
Gilbert, E. N., ``Tandem Conveyor Queues,'' Prob. Eng. Inf. Sci. 3 (1989), 517-536.
- 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.
- 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.
- Coffman, E. G., Jr., Fayolle, G. and
Mitrani, I., ``Two Queues with Alternating Service,'' Performance `87, North Holland
(1987), 227-239.
- 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.
- Coffman, E. G., Jr. and Mitrani, I.,
``A Characterization of Waiting Times Realizable by Single
Server Queues,'' Oper. Res., 28 (1980), 810-821.
- 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.
- 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)
- Coffman, E.G., Jr., and Michel, J.,
``Synthesis of a Feedback Queueing Discipline for Computer
Operation,'' J. Assoc. Comp.
Mach., 21 (1974), 329-339.
- 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.
- Coffman, E. G., Jr., ``Markov Chain
Analysis of Multiprogrammed Computer Systems,'' Naval Res. Log. Quart., 16 (1969), 175-197.
- 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.
- 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.
- Coffman, E. G., Jr., ``Analysis of Two
Time-Sharing Algorithms Designed for Limited Swapping,'' J. Assoc. Comp. Mach., 15 (1968), 341-353.
- 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.
- Coffman, E. G., Jr., and Kleinrock, L.,
``Feedback Queueing Models for Time-Shared Systems,'' Proc. Fifth International Teletraffic
Congress, 1967. (Expanded version below)
- Coffman, E. G., Jr., and Kleinrock, L.,
``Feedback Queueing Models for Time-Shared Systems,'' J. Assoc. Comp. Mach., 15 (1968), 549-576.
- Coffman, E. G., Jr., ``Bounds on
Parallel-Processing of Queues with Multiple Phase Jobs,'' Naval Res. Log. Quart., 14 (1967), 345-366.
- Coffman, E. G., Jr., and Kleinrock, L.,
``Distribution of Attained Service in Time-Sharing
Systems,'' J. Comp. Sys. Sci.,
1 (1967), 287-298.
- Coffman, E. G., Jr. and Wood, R. C.,
``Interarrival Statistics for Time Sharing Systems,'' Comm. Assoc. Comp. Mach., 14 (1966), 500-503.
- Coffman, E. G. Jr., ``The Study of
Multiprogramming Systems,'' Datamation, 1966.
- 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
- Baryshnikov, Y., Coffman, E. G., Jr.,
and Jelenkovic, P., ``A Limit Law for Reservation Systems,''
Bell Labs Tech. Rep., 1999.
- Coffman, E. G., Jr. and Jelenkovic, P.,
``Threshold Interval Packing and Reservation Algorithms,''
Performance Evaluation Review.
28 (2001), 9--11.
- Coffman, E.G.,Jr., Jelenkovic, P. and
Poonen, B., ``Reservation Probabilities,'' Advances in Performance Analysis,
2 (1999), 129--158.
File: pdf postscript
Computational
Geometry
- Coffman, E. G., Jr. and Gilbert, E. N.,
``Paths Through a Maze of Rectangles,'' Networks,
22 (1992), 349-367.
Storage Systems:
General
- 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.
- 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.
- 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).
- 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).
- Coffman, E.G., Jr., and Ryan, T.A., ``A
Problem in Multiprogrammed Storage Allocation,'' IEEE Trans. on Comp., C-23 (1974), 1116-1122.
- 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)
- 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
- Burnett, G.J., and Coffman, E.G., Jr.,
``Analysis of Interleaved Memory Systems Using Blockage
Buffers,'' Comm. Assoc. Comp.
Mach., 18 (1975), 91-95.
- Burnett, G.J., and Coffman, E.G., Jr.,
``A Combinatorial Problem Related to Interleaved Memories,''
J. Assoc. Comp. Mach., 20 (1973), 39-45.
- 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.
- 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
- 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.
- Coffman, E.G., Jr., and B. Randell,
``Performance Predictions for Extended Paged Memories,'' Acta Informatica, 1 (1971), 1-13.
- 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.
- 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)
- 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.
- 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
- Aven, O. I., Coffman, E. G., Jr. and
Kogan, Y. A., Stochastic Models of
Computer Storage, Reidel, Amsterdam, 1987.
- Coffman, E. G., Jr., ``Recent Progress
in the Performance Evaluation of Fundamental Allocation
Algorithms,'' Perf. Eval.
Rev., 12 (1984), 2-6.
Scheduling Theory:
Stochastic
- 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
- 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.
- 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.
- 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.
- Coffman, E. G., Jr., Flatto, L., and
Wright, P. E., ``Stochastic Machine Minimization with
Constant Service Times,'' Math.
Oper. Res., 18 (1993),
300-316.
- Coffman, E. G., Jr. and Liu, Z.,
``Optimal Scheduling of Jobs with Out-Forest Precedence
Constraints,'' Oper. Res., 40 (1992), Supplement 1, S67-S75.
- 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.
- 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.
- 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.
- 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
- Coffman, E. G., Jr., D. Dereniowski, and
W. Kubiak, ``An Efficient Algorithm for Finding Ideal Schedules," Acta Informatica, , 2011.
File: pdf
- Coffman, E. G., Jr., J. Sethuraman, and
V. Timkovsky, ``Ideal Preemptive Schedules on Two
Processors," Acta Informatica ,
39 (2003), 597-612.
File: pdf postscript
- 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).
- Coffman, E.G.,Jr. and Even, S., ``A
Note on Limited Preemption'' Parallel Processing Letters, 8 (1998), 3-6.
File: pdf postscript
- 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)
- 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.
- 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.
- 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.
- Baker, B.S. and Coffman, E.G., Jr.,
``Mutual Exclusion Scheduling,'' Theor. Comput. Sci., 162 (1996), 225--243.
File: pdf postscript
- 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.
- Coffman, E. G., Jr. and Langston, M.
A., ``A Performance Guarantee for Greedy Set Partitioning,''
Acta Informatica, 21 (1984), 409-415.
- 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.)
- 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)
- 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.
- 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)
- 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.
- Coffman, E.G., Jr., and Sethi, R.,
``Algorithms Minimizing Mean Flow Time: Schedule-Length
Properties,'' Acta Informatica,
6 (1976), 1-14.
- 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.
- Coffman, E.G., Jr., ``A Survey of
Mathematical Results in Flow-Time Sequencing for Computer
Systems,'' Proc. GI73,
Springer-Verlag (1973), 25-46.
- 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)
- Bruno, J., Coffman, E.G., Jr., and
Sethi, R., ``Algorithms for Reducing Mean Flow Times,'' Comm. Assoc. Comp. Mach., 17 (1974), 382-387.
- 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)
- Coffman, E.G., Jr., and Graham, R.L.,
``Optimal Scheduling of Two-Processor Systems,'' Acta Informatica 1 (1972), 200-213.
- 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.
- 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.
- 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)
- 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
- 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
- Coffman, E.G., Jr., Flatto, L. and
Whitt, W., ``Stochastic Limit Laws for Schedule Makespans''
Stochastic Models, 12 (1996), 215--243.
File: pdf postscript
- 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.
- 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.
- Coffman, E. G., Jr., and Gilbert, E.
N., ``Expected Relative Performance of List Scheduling
Rules,'' Oper. Res., 33 (1985), 548-561.
- 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.
- Chretienne, Ph., Coffman, E.G., Jr.,
Lenstra, J.K., and Liu, Z. (Editors), Scheduling Theory and Its
Applications, Wiley, Chichester, England (1995).
- 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.
- Coffman, E.G., Jr., Computer and Job-Shop Scheduling
Theory, John Wiley and Sons, 1975 (editor and
co-author). Russian and Polish translations.
- Coffman, E.G., Jr., ``Scheduling
Theory: Complexity and Optimal Algorithms,'' Proc. Texas Conf. on Computer
Science, Nov. 1975.
The Internet
- 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
- Constantinides, A. and Coffman, E., ``
Seamless Self-Assembly of Files in Cache Networks at Minimal
Storage Cost,'' (2009), submitted for publication.
File: postscript
- Constantinides, A. and Coffman, E., ``
Optimal Seamless Self-Assembly of Files in Linear
Networks," Optimization Letters, 1 (2007): 119-128.
File: postscript
- 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
- 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
- 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
- Coffman, E.G.,Jr., Jelenkovic, P., and
Momcilovic, P., ``The Dyadic Stream Merging Algorithm,'' J. Algorithms, 43(2002), 120--137.
- 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
- 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)
- 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.
- 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
- 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
- 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
- Coffman, E. G., Jr., Courtois, P.-J.
Gilbert, E. N., and Piret, P., ``A Distributed Clustering
Process,'' J. Appl. Prob., 28 (1991), 737-750.
- 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
- 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
- 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
- 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
- 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
- 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
- Coffman, E. G., Jr., ``Random Phenomena in Algorithmic Self Assembly:
Computing Times at Nanoscale,'' Hermis International Journal, 9 (2008), 9-22.
General
- 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.
- Coffman, E.G., Jr., Principles of Communication Systems: A
First Course , First draft, 2003, 86 pages.
File: postscript
- 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.
- 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.
- Coffman, E.G., Jr., Lenstra, J.K., and
Rinnooy Kan, Computing
(editors), Vol.3, Handbook of
Operations Research and Management Science, North
Holland, 1992.
|
|
|