The ordered covering problem
type: Item
instance of: scholarly article
title: The ordered covering problem
zbMATH Open document ID: 1459.05256
author: Yael Hitron
author: Uriel Feige
published in: Algorithmica
publication date: 2018-07-26T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6911192
zbMATH Keywords: polynomial time approximation algorithm
zbMATH Keywords: OC problem
MaRDI profile type: Publication
full work available at URL: s00453-017-0357-6
OpenAlex ID: W2746172223
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
cites work: On the hardness of approximating minimum vertex cover
cites work: Analytical approach to parallel repetition
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: A threshold of ln n for approximating set cover
cites work: Relations between average case complexity and approximation complexity
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Lower bounds on learning decision lists and trees
cites work: Which problems have strongly exponential complexity?
cites work: Approximation algorithms for combinatorial problems
cites work: Q4252414
cites work: A better approximation ratio for the vertex cover problem
cites work: On the power of unique 2-prover 1-round games
cites work: Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: On the hardness of approximating spanners
cites work: On the ratio of optimal integral and fractional covers
cites work: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
DOI: 10.1007/S00453-017-0357-6
Recommended article: Q4580330
Recommended article: The p-cover problem
Recommended article: Two methods of ordering the covering elements for the solution of the set covering problem
Recommended article: Q4552242
Recommended article: A Best Covering Problem.
Recommended article: Solution to the covering problem
Recommended article: Q3320395
Recommended article: The multicovering problem
Recommended article: Covering Problems
description: scientific article; zbMATH DE number 6911192