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

Noga Alon | Zendy; János Csirik | Zendy; S. V. Sevastianov | Zendy; Arjen P.A. Vestjens | Zendy; Gerhard J. Woeginger | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Noga Alon,

János Csirik,

S. V. Sevastianov,

Arjen P.A. Vestjens,

Gerhard J. Woeginger

Publication year - 1996

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/3-540-61680-2_71

Subject(s) - approximation algorithm , line (geometry) , mathematics , partition (number theory) , algorithm , combinatorics , discrete mathematics , geometry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research