Algorithms and complexity, proceedings vol:2653 pages:178-188
CIAC 2003 : Italian conference on algorithms and complexity No5, Rome , ITALIE date:28-30 May 2003
We study a number of retrieval problems that relate to effectively using the throughput of parallel disks. These problems can be formulated as assigning a maximum number of jobs,to machines of capacity two, where jobs are of size one or two that must satisfy assignment restrictions. We prove that the LP-relaxation of an integer programming formulation is half-integral, and derive an interesting persistency property. In addition, we derive 2/3-approximation results for two types of retrieval problems.