ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 53 Issue 1, January 2006

On the Sum-of-Squares algorithm for bin packing
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
Pages: 1-65
DOI: 10.1145/1120582.1120583
In this article we present a theoretical analysis of the online Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and...

A dichotomy theorem for constraint satisfaction problems on a 3-element set
Andrei A. Bulatov
Pages: 66-120
DOI: 10.1145/1120582.1120584
The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity and lead to...

A new average case analysis for completion time scheduling
Mark Scharbrodt, Thomas Schickinger, Angelika Steger
Pages: 121-146
DOI: 10.1145/1120582.1120585
We present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio---which is a typical worst case...

Hidden word statistics
Philippe Flajolet, Wojciech Szpankowski, Brigitte Vallée
Pages: 147-183
DOI: 10.1145/1120582.1120586
We consider the sequence comparison problem, also known as “hidden” pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A...

Limits on the ability of quantum states to convey classical messages
Ashwin Nayak, Julia Salzman
Pages: 184-206
DOI: 10.1145/1120582.1120587
We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in...