enter search term and/or author name
A measure & conquer approach for the analysis of exact algorithms
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch
Article No.: 25
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
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
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
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...