Access Restriction

Author Calinescu, Gruia ♦ Li, Minming
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Register Loading ♦ Linear Program ♦ Bank Requirement ♦ Load Instruction ♦ Valid Solution ♦ Valid Solution Associate ♦ Directed Graph ♦ Memory Bank Requirement ♦ Total Number ♦ Associated Load Instruction ♦ Approximation Algorithm ♦ Following Optimization Problem ♦ Start Vertex ♦ Specified Start Vertex ♦ Vertex Cover
Abstract We study the following optimization problem. The input is a number k and a directed graph with a specified “start ” vertex, each of whose vertices may have one “memory bank requirement”, an integer. There are k “registers”, labeled 1...k. A valid solution associates to the vertices with no bank requirement one or more “load instructions ” L[b,j], for bank b and register j, such that every directed trail from the start vertex to some vertex with bank requirement c contains a vertex u that has been associated L[c,i] (for some register i ≤ k) and no vertex following u in the trail has been associated an L[b,i], for any other bank b. The objective is to minimize the total number of associated load instructions. We give a k(k +1)-approximation algorithm based on linear programming rounding, with (k+1) being the best possible unless Vertex Cover has approximation 2−ǫ for ǫ> 0. We also present a O(klogn) approximation, with n being the number of vertices in the input directed graph. Based on the same linear program, another rounding method outputs a valid solution with objective at most 2k times the optimum for k registers, using 2k−1 registers. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2012-01-01