Approximation of a retrieval problem for parallel disks

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

doi:10.1007/3-540-44849-7_23

Approximation of a retrieval problem for parallel disks

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

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-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 language	English
Title of host publication	Algorithms and complexity
Subtitle of host publication	5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings
Editors	R. Petresch, G. Persiano, R. Silvestri
Place of Publication	Berlin
Publisher	Springer
Pages	178-188
ISBN (Electronic)	978-3-540-44849-5
ISBN (Print)	978-3-540-40176-6
DOIs	https://doi.org/10.1007/3-540-44849-7_23
Publication status	Published - 2003
Externally published	Yes
Event	5th Conference on Algorithms and Complexity (CIAC'03) - Rome, Italy Duration: 28 May 2003 → 30 May 2003 Conference number: 5 http://wwwusers.di.uniroma1.it/~ciac2003/

Publication series

Name	Lecture Notes in Computer Science
Volume	2653

Conference

Conference	5th Conference on Algorithms and Complexity (CIAC'03)
Abbreviated title	CIAC '03
Country/Territory	Italy
City	Rome
Period	28/05/03 → 30/05/03
Internet address	http://wwwusers.di.uniroma1.it/~ciac2003/

Access to Document

10.1007/3-540-44849-7_23

Cite this

Aerts, J., Korst, J., & Spieksma, F. C. R. (2003). Approximation of a retrieval problem for parallel disks. In R. Petresch, G. Persiano, & R. Silvestri (Eds.), Algorithms and complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings (pp. 178-188). (Lecture Notes in Computer Science; Vol. 2653). Springer. https://doi.org/10.1007/3-540-44849-7_23

@inbook{02b6a93395724f89a84807acbf0310ce,

title = "Approximation of a retrieval problem for parallel disks",

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.",

author = "J. Aerts and J. Korst and F.C.R. Spieksma",

year = "2003",

doi = "10.1007/3-540-44849-7\_23",

language = "English",

isbn = "978-3-540-40176-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "178--188",

editor = "R. Petresch and G. Persiano and Silvestri, \{R. \}",

booktitle = "Algorithms and complexity",

address = "Germany",

note = "5th Conference on Algorithms and Complexity (CIAC'03) , CIAC '03 ; Conference date: 28-05-2003 Through 30-05-2003",

url = "http://wwwusers.di.uniroma1.it/\textasciitilde{}ciac2003/",

}

Aerts, J, Korst, J & Spieksma, FCR 2003, Approximation of a retrieval problem for parallel disks. in R Petresch, G Persiano & R Silvestri (eds), Algorithms and complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings. Lecture Notes in Computer Science, vol. 2653, Springer, Berlin, pp. 178-188, 5th Conference on Algorithms and Complexity (CIAC'03) , Rome, Italy, 28/05/03. https://doi.org/10.1007/3-540-44849-7_23

Approximation of a retrieval problem for parallel disks. / Aerts, J.; Korst, J.; Spieksma, F.C.R.
Algorithms and complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings. ed. / R. Petresch; G. Persiano; R. Silvestri. Berlin: Springer, 2003. p. 178-188 (Lecture Notes in Computer Science; Vol. 2653).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Approximation of a retrieval problem for parallel disks

AU - Aerts, J.

AU - Korst, J.

AU - Spieksma, F.C.R.

N1 - Conference code: 5

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-44849-7_23

DO - 10.1007/3-540-44849-7_23

M3 - Chapter

SN - 978-3-540-40176-6

T3 - Lecture Notes in Computer Science

SP - 178

EP - 188

BT - Algorithms and complexity

A2 - Petresch, R.

A2 - Persiano, G.

A2 - Silvestri, R.

PB - Springer

CY - Berlin

T2 - 5th Conference on Algorithms and Complexity (CIAC'03)

Y2 - 28 May 2003 through 30 May 2003

ER -

Approximation of a retrieval problem for parallel disks

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this