On-line and off-line approximation algorithms for vector covering problems

Autor: Noga Alon, Arjen P. A. Vestjens, Leah Epstein, Yossi Azar, Gerhard J. Woeginger, Sergey V. Sevastianov, János Csirik
Přispěvatelé: Stochastic Operations Research, Combinatorial Optimization 1
Jazyk: angličtina
Rok vydání: 1996
Předmět:
Zdroj: Scopus-Elsevier
Algorithmica, 21(1), 104-118. Springer
Algorithms — ESA '96 ISBN: 9783540616801
ESA
Algorithms-ESA'96 (Proceedings Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996), 406-418
STARTPAGE=406;ENDPAGE=418;TITLE=Algorithms-ESA'96 (Proceedings Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996)
ISSN: 0302-9743
0178-4617
DOI: 10.1007/3-540-61680-2_71
Popis: 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. For the on-line 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 Frenk in [5] where it is claimed that, for d≥ 2 , no on-line algorithm can have a worst case ratio better than zero. Moreover, we prove that, for d≥ 2 , no on-line algorithm can have a worst case ratio better than 2/(2d+1) . For the off-line 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 .
Databáze: OpenAIRE
Externí odkaz: