Search ACM DL

Search Issue

enter search term and/or author name

**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...