Tech Report CS-91-18

Ordering Problems Approximated: Register Sufficiency, Single-Processor Scheduling and Interval Graph

Ajit Agrawal, Philip Klein and R. Ravi

March 1991


In this paper, we give the first poly-time approximation algorithms for three problems in combinatorial optimization. The first problem is register sufficiency where, given a computation dag, we are required to find the minimum number of registers needed to compute it. This problem arises in compiler optimization, in the task of register allocation. The second problem is single-processor scheduling to minimize weighted sum of completion times, subject to precedence constraints. The third problem, interval graph completion, is finding a minimum-size interval graph containing the input graph as a subgraph. All of the above problems are NP-complete; our algorithms output solutions that are within a polylogarithmic factor of optimal. To achieve these bounds, we make use of a technique developed and first applied by Leighton and Rao, together with a technique of Hansen.

(complete text in pdf)