Publication Date:
2015-06-19
Description:
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, \ldots , 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 \le 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 - {\epsilon }\) for \({\epsilon }〉 0\) . We also present a \(O(k \log n)\) 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.
Print ISSN:
0178-4617
Electronic ISSN:
1432-0541
Topics:
Computer Science
,
Mathematics
