Tight bounds on subexponential time approximation of set cover and related problems
type: Item
instance of: scholarly article
title: Tight bounds on subexponential time approximation of set cover and related problems
DOI: 10.1007/978-3-030-80879-2_11
author: Magnús M. Halldórsson
author: Guy Kortsarz
author: Marek Cygan
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2008.05374
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7495125
zbMATH Keywords: subexponential time algorithms
zbMATH Keywords: lower bounds
zbMATH Keywords: set cover
MaRDI profile type: Publication
OpenAlex ID: W3183852655
cites work: New tools and connections for exponential-time approximation
cites work: Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Exponential-time approximation of weighted set cover
cites work: Analytical approach to parallel repetition
cites work: The steiner problem in graphs
cites work: A threshold of ln n for approximating set cover
cites work: Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
cites work: O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
cites work: Polylogarithmic inapproximability
cites work: Which problems have strongly exponential complexity?
cites work: Approximation algorithms for combinatorial problems
cites work: Approximating the weight of shallow Steiner trees
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: Q2941638
cites work: Sub-constant error probabilistically checkable proof of almost-linear size
cites work: Q4231923
cites work: Q4228498
cites work: An analysis of the greedy algorithm for the submodular set covering problem
Recommended article: On approximation of the submodular set cover problem
Recommended article: Q4608053
Recommended article: Subexponential algorithms for partial cover problems
Recommended article: Efficient approximation of Min Set Cover by moderately exponential algorithms
Recommended article: Exponential-time approximation of weighted set cover
Recommended article: Partial sublinear time approximation and inapproximation for maximum coverage
Recommended article: Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Recommended article: Tight bounds for single-pass streaming complexity of the set cover problem
Recommended article: Tight approximation bounds for combinatorial frugal coverage algorithms
description: scientific article; zbMATH DE number 7495125