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)

Abstract

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
PublisherSpringer
Pages178-188
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
http://wwwusers.di.uniroma1.it/~ciac2003/

Publication series

NameLecture Notes in Computer Science
Volume2653

Conference

Conference5th Conference on Algorithms and Complexity (CIAC'03)
Abbreviated titleCIAC '03
CountryItaly
CityRome
Period28/05/0330/05/03
Internet address

Cite this