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. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1007/3-540-44849-7_23 | CIAC |
Keywords | Field | DocType |
3-approximation result,integer programming formulation,interesting persistency property,assignment restriction,retrieval problem,parallel disk,maximum number,lp relaxation,satisfiability | Speech processing,Combinatorics,Computer science,Algorithm,Image processing,Integer programming,Throughput,Linear programming relaxation,Channel capacity | Conference |
Volume | ISSN | ISBN |
2653 | 0302-9743 | 3-540-40176-8 |
Citations | PageRank | References |
4 | 0.60 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joep Aerts | 1 | 134 | 17.32 |
Jan Korst | 2 | 175 | 19.94 |
Frits C. R. Spieksma | 3 | 24 | 4.59 |