|
 
|
[CJPa08] Complexity results for the horizontal bar packing problem
Revue Internationale avec comité de lecture : Journal Information Processing Letters, vol. 108(6), pp. 356-359, 2008, (doi:10.1016/j.ipl.2008.07.007)
motcle:
Résumé:
The paper deals with the problem of packing a set of horizontal bars by taking into account some
constraints on the distance between two consecutive bars on the same row.
This problem is deeply connected with Discrete Tomography and it finds application in workforce
scheduling.
We study the complexity of the problem and show that, depending on the kind of
constraints considered, the problem can be polynomial or NP-Complete. We analyze in details the
case where a minimal distance between consecutive bars is required and propose a greedy algorithm
which solves this problem in polynomial time.
Equipe:
oc
BibTeX
| @article { | |||
| CJPa08, | |||
| title | = | "{Complexity results for the horizontal bar packing problem}", | |
| author | = | "M.-C. Costa and F. Jarray and C. Picouleau", | |
| journal | = | "Information Processing Letters", | |
| year | = | 2008, | |
| volume | = | 108, | |
| number | = | 6, | |
| pages | = | "356-359", | |
| doi | = | "10.1016/j.ipl.2008.07.007", | |
| } | |||
