Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 56 Issue 5, August 2009

A measure & conquer approach for the analysis of exact algorithms
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch
Article No.: 25
DOI: 10.1145/1552285.1552286

For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far...

On the expressiveness and complexity of randomization in finite state monitors
Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan
Article No.: 26
DOI: 10.1145/1552285.1552287

In this article, we introduce the model of finite state probabilistic monitors (FPM), which are finite state automata on infinite strings that have probabilistic transitions and an absorbing reject state. FPMs are a natural automata model...

On approximating the ideal random access machine by physical machines
Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik
Article No.: 27
DOI: 10.1145/1552285.1552288

The capability of the Random Access Machine (RAM) to execute any instruction in constant time is not realizable, due to fundamental physical constraints on the minimum size of devices and on the maximum speed of signals. This work explores...

A unified approach to scheduling on unrelated parallel machines
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Article No.: 28
DOI: 10.1145/1552285.1552289

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion...