Exponential-time approximation of weighted set cover
type: Item
instance of: scholarly article
title: Exponential-time approximation of weighted set cover
zbMATH Open document ID: 1202.68482
author: Marek Cygan
author: Łukasz Kowalik
author: Mateusz Wykurz
published in: Information Processing Letters
publication date: 2010-08-20T00:00:00Z
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5773833
zbMATH Keywords: exponential-time algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: set-cover
zbMATH Keywords: instance reduction
zbMATH Keywords: trade-off
MaRDI profile type: Publication
full work available at URL: j.ipl.2009.05.003
OpenAlex ID: W1985694287
cites work: Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
cites work: Efficient approximation of Min Set Cover by moderately exponential algorithms
cites work: Improved Parameterized Upper Bounds for Vertex Cover
cites work: MAX SAT approximation beyond the limits of polynomial-time approximation
cites work: Q4393480
cites work: A threshold of ln n for approximating set cover
cites work: Zero knowledge and the chromatic number
cites work: Measure and conquer
cites work: Expected Computation Time for Hamiltonian Path problem
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Confronting hardness using a hybrid approach
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.IPL.2009.05.003
description: scientific article; zbMATH DE number 5773833