Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation. (English) Zbl 1093.68145
Summary: The notion of approximability preserving reductions between different problems deserves special attention in approximability theory. These kinds of reductions allow us polynomial time conversion of some already known ’good’ approximation algorithms for some NP-hard problems into ones for some other NP-hard problems. In this context, we consider reductions for set covering and vertex covering hierarchies. Our results are then extended to hitting set and independent set hierarchies. Here, we adopt the differential approximation ratio that has the natural property to be stable under affine transformations of the objective function of a problem.
MSC:
| 68W25 | Approximation algorithms |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | Berge, Graphs and Hypergraphs (1973) |
| [2] | Garey M. R., A Guide to the Theory of NP-Completeness (1979) |
| [3] | DOI: 10.1016/0022-0000(91)90023-X · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X |
| [4] | Orponen P., Technical Report G-1987-28 (1987) |
| [5] | Trevisan L., PhD thesis (1997) |
| [6] | DOI: 10.1137/0403025 · Zbl 0699.68077 · doi:10.1137/0403025 |
| [7] | DOI: 10.1016/0304-3975(95)00060-7 · Zbl 0871.90069 · doi:10.1016/0304-3975(95)00060-7 |
| [8] | Paschos V. TH., Foundations Computing Decision Sci. 20 pp 49– (1995) |
| [9] | DOI: 10.1016/0022-0000(80)90046-X · Zbl 0441.68049 · doi:10.1016/0022-0000(80)90046-X |
| [10] | DOI: 10.1016/S0304-3975(97)00099-6 · Zbl 0912.68061 · doi:10.1016/S0304-3975(97)00099-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
