On-Line and Off-Line Approximation Algorithms for Vector Covering Problems

TitleOn-Line and Off-Line Approximation Algorithms for Vector Covering Problems
Publication TypeJournal Article
Year of Publication1998
AuthorsAlon N., Azar Y., Csirik J., Epstein L., Sevastianov S.V, Vestjens A.PA, Woeginger G.J
JournalAlgorithmica
Volume21
Pagination104–118
Date PublishedMay
ISSN1432-0541
Abstract

This paper deals with vector covering problems in d -dimensional 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.

URLhttps://doi.org/10.1007/PL00009203
DOI10.1007/PL00009203