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