On the positive-negative partial set cover problem

DOI10.1016/J.IPL.2008.05.007zbMATH Open1191.68251OpenAlexW2089573024MaRDI QIDQ975452FDOQ975452

Authors: Pauli Miettinen 

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.05.007

Recommendations

• A Unified Approach to Approximating Partial Covering Problems
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• Computing small partial coverings
• On partial covering for geometric set systems
• A threshold of ln n for approximating set cover

zbMATH Keywords

approximation algorithmsset covercombinatorial problemshardness of approximation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Database theory (68P15)

Cites Work

• Parametrized complexity theory.
• Title not available (Why is that?)
• On the hardness of approximating label-cover
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• Title not available (Why is that?)

Cited In (8)

• Red blue set cover problem on axis-parallel hyperplanes and other objects
• Title not available (Why is that?)
• Evader interdiction: algorithms, complexity and collateral damage
• Comparing apples and oranges: measuring differences between exploratory data mining results
• Hybrid ASP-based approach to pattern mining
• A simple approximation algorithm for minimum weight partial connected set cover
• Logical correctors in the problem of classification by precedents
• On a generalized sequential partially covering problem

This page was built for publication: On the positive-negative partial set cover problem

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