Approximating subdense instances of covering problems
From MaRDI portal
Abstract: We study approximability of subdense instances of various covering problems on graphs, defined as instances in which the minimum or average degree is Omega(n/psi(n)) for some function psi(n)=omega(1) of the instance size. We design new approximation algorithms as well as new polynomial time approximation schemes (PTASs) for those problems and establish first approximation hardness results for them. Interestingly, in some cases we were able to prove optimality of the underlying approximation ratios, under usual complexity-theoretic assumptions. Our results for the Vertex Cover problem depend on an improved recursive sampling method which could be of independent interest.
Recommendations
- On approximation of the submodular set cover problem
- scientific article; zbMATH DE number 1163714
- Subexponential algorithms for partial cover problems
- Subexponential algorithms for partial cover problems
- On covering approximation subspaces
- Revisiting the approximation bound for stochastic submodular cover
- Partial sublinear time approximation and inapproximation for maximum coverage
- Approximating the dense set-cover problem
- Approximation algorithms for partial covering problems
- Generalized submodular cover problems and applications
Cites work
- Approximating vertex cover on dense graphs
- Connected vertex covers in dense graphs
- scientific article; zbMATH DE number 1163714 (Why is no real title available?)
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Steiner trees in uniformly quasi-bipartite graphs.
- The steiner problem in graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(8)- Improved approximation for spanning star forest in dense graphs
- On covering approximation subspaces
- Approximating edge dominating set in dense graphs
- On the approximability of dense Steiner problems
- scientific article; zbMATH DE number 1163714 (Why is no real title available?)
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
- A Tight Bound for Stochastic Submodular Cover
- Approximating edge dominating set in dense graphs
This page was built for publication: Approximating subdense instances of covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840726)
