The ordered covering problem

DOI10.1007/S00453-017-0357-6zbMATH Open1459.05256OpenAlexW2746172223MaRDI QIDQ722532FDOQ722532

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

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

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)

Cites Work

• A threshold of ln n for approximating set cover
• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Which problems have strongly exponential complexity?
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• 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
• On the hardness of approximating minimum vertex cover
• A better approximation ratio for the vertex cover problem
• On the power of unique 2-prover 1-round games
• Analytical approach to parallel repetition
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Title not available (Why is that?)
• On the hardness of approximating spanners
• Lower bounds on learning decision lists and trees
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

Cited In (4)

• Sherali-Adams integrality gaps matching the log-density threshold
• Title not available (Why is that?)
• Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
• Two methods of ordering the covering elements for the solution of the set covering problem

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)