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

DOI10.1007/PL00009203MaRDI QIDQ1386465zbMATH OpenFDO

Authors Noga Alon, Arjen P. A. Vestjens, Gerhard J. Woeginger, Yossi Azar, János Csirik, Leah Epstein, Sergey Sevastyanov

Publication date 1 October 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009203

zbMATH Keywords

vector covering problems

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• On-line and off-line approximation algorithms for vector covering problems
• scientific article; zbMATH DE number 1798171
• Online variable sized covering

Cited in

(14)

• The skiving stock problem and its relation to hypergraph matchings
• Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case
• Online variable sized covering
• Lower bounds for online bin covering-type problems
• Approximation and online algorithms for multidimensional bin packing: a survey
• Bin covering with cardinality constraints
• There is no asymptotic PTAS for two-dimensional vector packing
• On-line and off-line approximation algorithms for vector covering problems
• Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory
• scientific article; zbMATH DE number 7559382 (Why is no real title available?)
• There is no APTAS for 2-dimensional vector bin packing: revisited
• Exact combinatorial algorithms for solving the bin covering problems with strong divisibility and rejection profit
• On the sum minimization version of the online bin covering problem
• Mean analysis of an online algorithm for the vertex cover problem

This page was built for publication: On-line and off-line approximation algorithms for vector covering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386465)