Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems

DOI10.1016/j.jda.2006.03.008zbMath1137.68627OpenAlexW1981873012MaRDI QIDQ924541

David Peleg

Publication date: 16 May 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.03.008

zbMATH Keywords

approximation algorithmslabel coverMax-Rep problemred-blue set cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (13)

Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Secluded connectivity problems ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ An improved algorithm for the red-blue hitting set problem with the consecutive ones property ⋮ Improved approximation algorithms for label cover problems ⋮ Logical correctors in the problem of classification by precedents ⋮ The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem ⋮ Improved approximation algorithms for projection games ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On the positive-negative partial set cover problem ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Approximating Component Selection with General Costs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating label-cover
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Minimum propositional proof length is NP-hard to linearly approximate
• A Greedy Heuristic for the Set-Covering Problem
• Intractability of assembly sequencing: Unit disks in the plane
• On the hardness of approximating spanners

This page was built for publication: Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems