Approximation of a retrieval problem for parallel disks

J. Aerts, J. Korst, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

4 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithms and complexity
Subtitle of host publication5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings
EditorsR. Petresch, G. Persiano, R. Silvestri
Place of PublicationBerlin
ISBN (Electronic)978-3-540-44849-5
ISBN (Print)978-3-540-40176-6
Publication statusPublished - 2003
Externally publishedYes
Event5th Conference on Algorithms and Complexity (CIAC'03) - Rome, Italy
Duration: 28 May 200330 May 2003
Conference number: 5

Publication series

NameLecture Notes in Computer Science


Conference5th Conference on Algorithms and Complexity (CIAC'03)
Abbreviated titleCIAC '03
Internet address

Cite this