The ordered covering problem

DOI10.1007/S00453-017-0357-6MaRDI QIDQ722532zbMATH OpenOpenAlexFDO

Authors Yael Hitron, Uriel Feige

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

zbMATH Keywords

polynomial time approximation algorithmOC problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The covering problem
• The p-cover problem
• Two methods of ordering the covering elements for the solution of the set covering problem
• scientific article; zbMATH DE number 1792649
• A Best Covering Problem.
• Solution to the covering problem
• scientific article; zbMATH DE number 3851110
• The multicovering problem
• Covering Problems

Cites work

• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A better approximation ratio for the vertex cover problem
• A threshold of ln n for approximating set cover
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Analytical approach to parallel repetition
• Approximation algorithms for combinatorial problems
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Lower bounds on learning decision lists and trees
• On the hardness of approximating minimum vertex cover
• On the hardness of approximating spanners
• On the power of unique 2-prover 1-round games
• On the ratio of optimal integral and fractional covers
• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Which problems have strongly exponential complexity?

Cited in

(4)

• Two methods of ordering the covering elements for the solution of the set covering problem
• Sherali-Adams integrality gaps matching the log-density threshold
• Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
• scientific article; zbMATH DE number 1792649 (Why is no real title available?)

This page was built for publication: The ordered covering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722532)