Register Loading via Linear Programming

We study the following optimization problem. The input is a number $$k$$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$$k “registers”, labeled $$1, \ldots , k$$1,…,k. A valid solution associates to the vertices with no bank requirement one or more “load instructions” $$L[b,j]$$L[b,j], for bank $$b$$b and register $$j$$j, such that every directed trail from the start vertex to some vertex with bank requirement $$c$$c contains a vertex $$u$$u that has been associated $$L[c,i]$$L[c,i] (for some register $$i \le k$$i≤k) and no vertex following $$u$$u in the trail has been associated an $$L[b,i]$$L[b,i], for any other bank $$b$$b. The objective is to minimize the total number of associated load instructions. We give a $$k(k+1)$$k(k+1)-approximation algorithm based on linear programming rounding, with $$(k+1)$$(k+1) being the best possible unless Vertex Cover has approximation $$2 - {\epsilon }$$2-ϵ for $${\epsilon }> 0$$ϵ>0. We also present a $$O(k \log n)$$O(klogn) approximation, with $$n$$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$$2k times the optimum for $$k$$k registers, using $$2k-1$$2k-1 registers.