Efficient Performance Analysis of Asynchronous Systems Based on Periodicity (2009)
This paper presents an efficient method for the performance analysis and optimization of asynchronous systems. An asynchronous system is modeled as a marked graph with probabilistic delay...
Scheduling Two-Point Stochastic Jobs (2008)
Sem Borst, John Bruno, E. G. Coffman, Steven Phillips, Sem Borst, John Bruno, ...
Processor shadowing: Maximizing expected throughput in fault-tolerant systems (2008)
J. L. Bruno, E. G. Coffman, J. C. Lagarias, T. J. Richardson, P. W. Shor
This paper studies parallel processing as a device for increasing fault tolerance. In the first of two basic models, a single job with a given running time is to be run on a finite set of processors;...
E. G. Coffman, Zihui Ge, Don Towsley, Vishal Misra
Recent studies [1] have revealed vulnerabilities in the routing infrastructure of the Internet. It has been conjectured that these vulnerabilities could lead to cascading failures. In this paper we...
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
Abstract. We consider the one-dimensional bin packing problem under the discrete uniform distributions U{j, k}, 1 ≤ j ≤ k − 1, in which the bin capacity is k and item sizes are chosen uniformly...
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P.W. Shor, ...
We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution Ufj; kg, 1 ! j k; where each item size in f1=k; 2=k; :...
An Asymptotic Analysis of Closed Queueing Networks with Branching Populations (2007)
N. Bayer, N. Bayer, E. G. Coffman, E. G. Coffman, Y. A. Kogan, Y. A. Kogan
An asymptotic analysis of closed queueing networks with branching
Perfect packing theorems and the average-case behavior of optimal and online bin packing (2007)
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
Abstract. We consider the one-dimensional bin packing problem under the discrete uniform distributions U{j, k}, 1
An Asymptotic Probabilistic Analysis of Vehicle Routing (2007)
Recently, Simchi-Levi and Bramel (1990) analyzed an interesting probability model of the following routing problem. Consider a set of points p i = (x i; y i), 0 i n, in the plane, where p 0 denotes...
E. G. Coffman, Anja Feldmann, Nabil Kahale, Bjorn Poonen
We study call admission rates in a linear communication network with each call identified by an arrival time, duration, bandwidth requirement, and origin-destination pair. Network links all have the...
Optimal carrier sharing in wireless TDMA (2007)
S. C. Borst, E. G. Coffman, E. N. Gilbert, P. A. Whiting, P. M. Winkler
To improve efficiency, we allow a carrier in a TDMA (Time Division Multiple Access) network to be shared by adjacent cells. This sharing of time slots is seriously hampered by the lack of...
E. G. Coffman, Leopold Flatto, A. Y. Kreinin
Many computer applications require long computations lasting anywhere from several days to even years. Examples, to name just a few, include cryptography, combinatorial optimization, and asymptotics...
E. G. Coffman, Anja Feldmann, Nabil Kahale, Bjorn Poonen
We study call admission rates in a linear communication network with each call identified by an arrival time, duration, bandwidth requirement, and origin-destination pair. Network links all have the...
E. G. Coffman, A. A. Puhalskii, M. I. Reiman
In polling systems, M 2 queues are visited by a single server in cyclic order. These systems model such diverse applications as token-ring communication networks and cyclic production systems. We...
E. G. Coffman, A. A. Puhalskii, M. I. Reiman
This paper studies the classical polling model under the exhaustive-service assumption; such models continue to be very useful in performance studies of computer/communication systems. The analysis...
E. G. Coffman, Nabil Kahale, F. T. Leighton
We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random...
Sid Browne, E. G. Coffman, E. N. Gilbert, Paul E. Wright
Customers, in a Poisson stream at rate, enter an infinite-server queue. Customer service times are independent and uniformly distributed on [0; s], s? 0. Gated service is performed in stages as...
Approximation Algorithms for Extensible Bin Packing (2007)
E. G. Coffman, George S. Lueker
In a variation of bin packing called extensible bin packing, the number of bins to use is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost...
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution Ufj; kg, 1! j k; where each item size in f1=k; 2=k; :...
The Maximum of a Random Walk and Its Application to Rectangle Packing (2007)
E. G. Coffman, Leopold Flatto, Micha Hofri
Let S 0; : : : ; Sn be a symmetric random walk that starts at the origin (S 0 = 0), and takes steps uniformly distributed on [\Gamma1; +1]. We study the large-n behavior of the expected maximum...
Space filling and depletion (2007)
Yuliy Baryshnikov, E. G. Coffman, Predrag Jelenkovi C
Abstract. For a given k 1, subintervals of a given interval [0; X] arrive at random and are accepted (allocated) so long as they overlap fewer than k subintervals already accepted. Subintervals not...
The Dyadic Algorithm for Stream Merging (2007)
E. G. Coffman, Jelenković Petar Momčilović
We study the stream merging problem for media-on-demand servers. Clients requesting media from the server arrive by a Poisson process, and delivery to the clients starts immediately. Clients are...
1 Packing Random Intervals (2007)
E. G. Coffman, Bjorn Poonen, Peter Winkler
Abstract. Let n random intervals I 1; : : : ; I n be chosen by selecting endpoints independently from the uniform distribution on [0; 1]. A packing is a pairwise disjoint subset of the intervals; its...
Euclidean Matching: Let d(P \Gamma (2007)
Since the pioneering work on multi-dimensional packing by Karp, Luby, and MarchettiSpaccamela [KLM] in 1984, stochastic matching problems in two and three dimensions have surfaced in the analysis of...
E. G. Coffman, Steven Phillips, Sem Borst, Sem Borst, John Bruno, John Bruno
Simple optimal policies are known for the problem of scheduling jobs to minimize expected makespan on two parallel machines when the job running-time distribution has a monotone hazard rate. But no...
Reservation Probabilities (2007)
E. G. Coffman, Predrag Jelenkovic, Bjorn Poonen
Requests for a given resource arrive in a rate- Poisson stream, each specifying a future time interval to be reserved for its use of the resource. The advance notices and the requested intervals are...
modules. Computer Aided Design, 8:27–33, 1976. (2006)
Vladimir Gantovnik, Santosh Tiwari, P. Chen, Z. Fu, A. Lim, E. G. Coffman, ...
[1] M. Adomowicz and A. Albano. Nesting two-dimensional shapes in rectangular
Content distribution for seamless transmission (2004)
E. G. Coffman, Constantinides Dan, Rubenstein Bruce Shepherd
We introduce a new paradigm in information transmission, the concept of SEAMLESS TRANSMISSION, whereby any client in a network requesting a file starts receiving it immediately, and experiences no...
E. G. Coffman, J. Sethuraman, V. G. Timkovsky
Abstract. An ideal schedule minimizes both makespan and total flow time. It is known that the Coffman-Graham algorithm [Acta Informatica 1, 200– 213, 1972] solves in polynomial time the problem of...
Provably efficient stream merging (2001)
E. G. Coffman, Jelenkovi Petar Mom
We investigate the stream merging problem for mediaon-demand servers. Clients requesting media from the server arrive by a Poisson process, and delivery to the clients starts immediately. Clients are...
The interval packing process of linear networks (1999)
Introduction. Start with the following elegant interval packing (IP) problem. Let random subintervals arrive at a service facility in a rate- Poisson stream; a random subinterval is simply the...
Packing random rectangles (1999)
E. G. Coffman, George S. Lueker, Joel Spencer, Peter M. Winkler
A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from [0; 1]. We prove that the number C n of...
Packing Random Rectangles (1999)
E. G. Coffman, George S. Lueker, Joel Spencer, Peter M. Winkler
A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from [0; 1]. We prove that the number of...
Controlling Robots in Web Search Engines (1999)
J. Talim, Z. Liu, P. Nain, E.G. Coffman
Robots are deployed by a Web search engine for collecting information from different Web servers in order to maintain the currency of its data base of Web pages. In this paper, we investigate the...
Optimizing the Number of Robots for Web Search Engines (1999)
J. Talim, Z. Liu, P. Nain, E.G. Coffman
Robots are deployed by a Web search engine for collecting information from different Web servers in order to maintain the currency of its data base of Web pages. In this paper, we investigate the...
Performance of the Move-To-Front Algorithm with Markov-Modulated Request Sequences (1999)
E. G. Coffman, Predrag Jelenkovic
We study the classical move-to-front (MTF) algorithm for self-organizing lists within the Markov-modulated request (MMR) model. Such models are useful when list accesses are generated within a...
Optimal Robot Scheduling for Web Search Engines (1997)
Coffman, E. G., Liu, Zhen, Weber, Richard R.
A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions $r_i$ of time...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman, E. G., Flajolet, Philippe, Flatto, Leopold, Hofri, Micha
We consider a symmetric random walk of length $n$ that starts at the origin and takes steps uniformly distributed on the real interval $[-1,+1]$. We study the large-$n$ behavior of the expected...
Optimal Robot Scheduling for Web Search Engines (1997)
Coffman, E. G., Liu, Zhen, Weber, Richard R.
A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions $r_i$ of time...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman, E. G., Flajolet, Philippe, Flatto, Leopold, Hofri, Micha
We consider a symmetric random walk of length $n$ that starts at the origin and takes steps uniformly distributed on the real interval $[-1,+1]$. We study the large-$n$ behavior of the expected...
E. G. Coffman, E. G. Coffman, D. S. Johnson, D. S. Johnson, L. A. Mcgeoch, L. A. Mcgeoch, ...
This is for the abstract page
An approximate model of processor communication rings under heavy load (1997)
E. G. Coffman, L. Flatto, E. N. Gilbert, A. G. Greenberg
A communication ring of N cells rotates unidirectionally in discrete steps, carrying messages (packets) among N processors at fixed locations around the ring. Each cell holds only one packet. A...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
E. G. Coffman, Philippe Flajolet, E. G. Coffman, Leopold Flatto, Leopold Flatto, Micha Hofri, ...
: We consider a symmetric random walk of length n that starts at the origin and takes steps uniformly distributed on the real interval [\Gamma1; +1]. We study the large-n behavior of the expected...
Optimal Robot Scheduling for Web Search Engines (1997)
E.G. Coffman, Zhen Liu, Richard R. Weber
A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions r i of time pages...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
E. G. Coffman, Philippe Flajolet, Leopold Flatto, Micha Hofri
Let S 0 ; : : : ; S n be a symmetric random walk that starts at the origin (S 0 = 0), and takes steps uniformly distributed on [\Gamma1; +1]. We study the large-n behavior of the expected maximum...
Packing Random Intervals On-Line (1997)
E. G. Coffman, Leopold Flatto, Predrag Jelenkovic, Flatto Predrag Jelenkovi'c, ...
Starting at time 0, unit-length intervals arrive and are placed on the positive real line by a unitintensity Poisson process in two dimensions; the probability of an interval arriving in the time...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman Philippe, E. G. Coffman, Leopold Flatto, Leopold Flatto, Micha Hofri, Micha Hofri
: We consider a symmetric random walk of length n that starts at the origin and takes steps uniformly distributed on the real interval [\Gamma1; +1]. We study the large-n behavior of the expected...
Stochastic limit laws for schedule makespans (1996)
E. G. Coffman, Leopold Flatto, Ward Whitt
processes, superposition A basic multiprocessor version of the makespan scheduling problem requires that n tasks be scheduled on m identical processors so as to minimize the latest task finishing...
Bin Packing with Discrete Item Sizes, Part II: Tight Bounds on First Fit (1996)
E. G. Coffman, D. S. Johnson, P. W. Shor, R. R. Weber
In the bin packing problem, a list L of n items is to be packed into a sequence of unit capacity bins with the goal of minimizing the number of bins used. First Fit (FF) is one of the most natural...
Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times (1996)
E. G. Coffman, Nabil Kahale, F. T. Leighton
We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random...
Some graph coloring models for cyclic scheduling (1995)
Solot, P., De Werra, D., Chrétienne, P., Coffman, E. G. Jr., Lenstra, J. K., Liu, Z.
W.: Recent asymptotic results in the probabilistic analysis of schedule makespans (1995)
Makespan scheduling problems are in the mainstream of operations research, industrial engineering, and computer science. A basic multiprocessor version requires that n tasks be scheduled on m...
A Stochastic Checkpoint Optimization Problem (1993)
E. G. Coffman, E. G. Coffman, Leopold Flatto, Leopold Flatto, Paul E. Wright, Paul E. Wright
We study an abstract moving-server system that models several computer applications, including software debugging and accessing compressed data. In this model, the server moves on the unit interval...
Probabilistic analysis of packing and related partitioning problems (1992)
E. G. Coffman, D. S. Johnson, P. W. Shor, G. S. Lueker
In the last 10 years there have been major advances in the average-case analysis of bin-packing, scheduling, and similar partitioning problems in one and two dimensions. These problems are drawn from...
A problem of increasing importance in the design of large multiprogramming systems is the, so-called, deadlock or deadly-embrace problem. In this arliele we survey the work that has been done on the...