Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations

## Detail(s)

Original language English 1011-1032 Algorithmica 72 4 Published - 30 May 2014

## Abstract

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.

## Research Area(s)

• Bank selection, Linear programming, Randomized rounding, Register allocation

## Citation Format(s)

[ RIS ] [ BibTeX ]