Paper Info
Title
On-line and Off-line Approximation Algorithms for Vector Covering Problems
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 o-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 (1990) 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 ford 2, no on-line algorithm can have worst case ratio better than 2=(2d + 1). For the o-line version, we derive polynomial time approximation algorithms with worst case guarantee
Year
DOI
Venue
1996
10.1007/PL00009203
Algorithmica
Keywords
Field
DocType
Key words. Approximation algorithm,Worst case ratio,Competitive analysis,On-line algorithm,Packing problem,Covering problem.
Approximation algorithm,Discrete mathematics,Combinatorics,Packing problems,Upper and lower bounds,Vector calculus,Partition (number theory),Mathematics,Competitive analysis,Covering problems,Computational complexity theory
Conference
Volume
Issue
ISSN
21
1
0178-4617
Citations 
PageRank 
References 
9
1.58
11
Authors
7
Name
Order
Citations
PageRank
Noga Alon1104681688.16
Yossi Azar23330365.24
János Csirik391370.15
Leah Epstein41163104.95
Sergey V. Sevastianov5667.09
Arjen P. A. Vestjens617416.24
Gerhard Woeginger74176384.37