The ordered covering problem
From MaRDI portal
Publication:722532
DOI10.1007/s00453-017-0357-6zbMath1459.05256OpenAlexW2746172223MaRDI QIDQ722532
Publication date: 26 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0357-6
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Which problems have strongly exponential complexity?
- Lower bounds on learning decision lists and trees
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Detecting high log-densities
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- A threshold of ln n for approximating set cover
- Relations between average case complexity and approximation complexity
- On the power of unique 2-prover 1-round games
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Analytical approach to parallel repetition
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- On the hardness of approximating spanners
This page was built for publication: The ordered covering problem
