60
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa

&
Pages 569-582 | Received 27 Aug 2003, Accepted 17 Dec 2003, Published online: 12 May 2010

References

  • Berge C. (1973) Graphs and Hypergraphs North Holland Amsterdam
  • Garey M. R. Johnson D. S. (1979) Computers and intractability A Guide to the Theory of NP-Completeness W. H. Freeman San Francisco
  • Papadimitriou , C. H. and Yannakakis , M. (1991) . Optimization, approximation and complexity classes . J. Comput. System Sci. , 43 : 425 – 440 .
  • Orponen P. Mannila H. (1987) On approximation preserving reductions: complete problems and robust measures Technical Report G-1987-28 Department of Computer Science, University of Helsinki Finland
  • Trevisan L. (1997) Reduction and (non-)Approximability PhD thesis Università degli Studi di Roma “La Sapienza“
  • Simon , H. U. (1990) . On approximate solutions for combinatorial optimization problems . SIAM J. Disc. Math. , 3 ( 2 ) : 294 – 310 .
  • Demange , M. and Paschos , V. TH. (1996) . On an approximation measure founded on the links between optimization and polynomial approximation theory . Theor. Comput. Sci. , 158 : 117 – 141 .
  • Paschos , V. TH. and Renotte , L. (1995) . Approximability preserving reductions for NP-complete problems . Foundations Computing Decision Sci. , 20 ( 1 ) : 49 – 71 .
  • Ausiello , G. , D'Atri , A. and Protasi , M. (1980) . Structure preserving reductions among convex optimization problems . J. Comput. System Sci. , 21 : 136 – 153 .
  • Demange , M. , Grisoni , P. and Paschos , V. TH. (1998) . Differential approximation algorithms for some combinatorial optimization problems . Theor. Comput. Sci. , 209 : 107 – 122 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.