Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 44 Issue 3, May 1997

On becoming editor-in-chief of JACM
Joeseph Halpern
Pages: 363-365
DOI: 10.1145/258128.268577

Exponential bounds with applications to call admission
Zhen Liu, Philippe Nain, Don Towsley
Pages: 366-394
DOI: 10.1145/258128.258129
In this paper, we develop a framework for computing upper and lower bounds of an exponential form for a large class of single resource systems with Markov additive inputs. Specifically, the bounds are on quantities such as backlog, queue length,...

Mesh refinement via bidirected flows: modeling, complexity, and computational results
Rolf H. Höhring, Matthias Müller-Hannemann, Karsten Wiehe
Pages: 395-426
DOI: 10.1145/258128.258174
We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface of a workpiece, into quadrilaterals so that the...

How to use expert advice
Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, Manfred K. Warmuth
Pages: 427-485
DOI: 10.1145/258128.258179
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence...

On-line routing of virtual circuits with applications to load balancing and machine scheduling
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
Pages: 486-504
DOI: 10.1145/258128.258201
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required bandwidth. We...

On the power and limitations of strictness analysis
R. Sekar, I. V. Ramakrishnan, P. Mishra
Pages: 505-525
DOI: 10.1145/258128.258212
Strictness analysis is an important technique for optimization of lazy functional languages. It is well known that all strictness analysis methods are incomplete, i.e., fail to report some strictness properties. In this paper,...