Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
type: Item
instance of: scholarly article
title: Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
zbMATH Open document ID: 1137.68627
author: David Peleg
published in: Journal of Discrete Algorithms
publication date: 2008-05-16T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5276088
zbMATH Keywords: label cover
zbMATH Keywords: red-blue set cover
zbMATH Keywords: Max-Rep problem
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: j.jda.2006.03.008
OpenAlex ID: W1981873012
cites work: Minimum propositional proof length is NP-hard to linearly approximate
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Q4952637
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: On the hardness of approximating label-cover
cites work: Q2728855
cites work: Q2754183
cites work: Intractability of assembly sequencing: Unit disks in the plane
cites work: On the hardness of approximating spanners
DOI: 10.1016/J.JDA.2006.03.008
description: scientific article; zbMATH DE number 5276088