TY - GEN
T1 - On-line and off-line approximation algorithms for vector covering problems
AU - Alon, Noga
AU - Csirik, János
AU - Sevastianov, Sergey V.
AU - Vestjens, Arjen P.A.
AU - Woeginger, Gerhard J.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - This paper deals with vector covering problems in ddimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1] d. The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-fine version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d ≥ 2 dimensions. This result contradicts a statement of Csirik and Freak (1990) in [5] where it is claimed that for d ≥ 2, no on-line algorithm can have a worst case ratio better than zero. For the off-fine version, we derive polynomial time approximation algorithms with worst case guarantee Ω (1/log d). For d = 2, we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2. Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d ≥ 2.
AB - This paper deals with vector covering problems in ddimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1] d. The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-fine version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d ≥ 2 dimensions. This result contradicts a statement of Csirik and Freak (1990) in [5] where it is claimed that for d ≥ 2, no on-line algorithm can have a worst case ratio better than zero. For the off-fine version, we derive polynomial time approximation algorithms with worst case guarantee Ω (1/log d). For d = 2, we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2. Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d ≥ 2.
KW - Approximation algorithm
KW - Covering problem
KW - On-line algorithm
KW - Packing problem
KW - Worst case ratio
UR - http://www.scopus.com/inward/record.url?scp=0344750918&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0344750918&partnerID=8YFLogxK
U2 - 10.1007/3-540-61680-2_71
DO - 10.1007/3-540-61680-2_71
M3 - Conference contribution
AN - SCOPUS:0344750918
SN - 3540616802
SN - 9783540616801
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 406
EP - 418
BT - Algorithms - ESA 1996 - 4th Annual European Symposium, Proceedings
A2 - Diaz, Josep
A2 - Serna, Maria
PB - Springer Verlag
T2 - 4th European Symposium on Algorithms, ESA 1996
Y2 - 25 September 1996 through 27 September 1996
ER -