Approximability of hard combinatorial optimization problems: an introduction

[1] Ausiello G.(1995)Approximate solution of NPO problems Theoretical Comput. Sci. 150 1-55

[2] Crescenzi P.(1980)Structure preserving reductions among convex optimization problems J. Comput. Syst. Sci. 21 136-153

[3] Protasi M.(1979)A greedy heuristic for the set covering problem Math. Oper. Res. 4 233-235

[4] Ausiello G.(1982)On the worst-case performance of some algorithms for the asymmetric TSP Networks 12 23-39

[5] D'Atri A.(1994)A short note on the approximability of the maximum leaves spanning tree problem Information Process. Letters 52 45-49

[6] Protasi M.(1997)On the approximability of some maximum spanning tree problems Theoretical Comput. Sci. 181 107-118

[7] Chv´atal V.(1978)Strong NP-completeness results: motivation, examples, and implications J. ACM 25 499-508

[8] Frieze A.M.(1976)The complexity of near-optimal graph coloring J. ACM 23 43-49

[9] Galbiati G.(1974)Approximation algorithms for combinatorial problems J. Comput. Syst. Sci. 9 256-278

[10] Maffioli F.(1994)Logical definability of NP optimization problems Inform. and Comput. 115 321-353

[1] Ausiello G.(1995)Approximate solution of NPO problems Theoretical Comput. Sci. 150 1-55

[2] Crescenzi P.(1980)Structure preserving reductions among convex optimization problems J. Comput. Syst. Sci. 21 136-153

[3] Protasi M.(1979)A greedy heuristic for the set covering problem Math. Oper. Res. 4 233-235

[4] Ausiello G.(1982)On the worst-case performance of some algorithms for the asymmetric TSP Networks 12 23-39

[5] D'Atri A.(1994)A short note on the approximability of the maximum leaves spanning tree problem Information Process. Letters 52 45-49

[6] Protasi M.(1997)On the approximability of some maximum spanning tree problems Theoretical Comput. Sci. 181 107-118

[7] Chv´atal V.(1978)Strong NP-completeness results: motivation, examples, and implications J. ACM 25 499-508

[8] Frieze A.M.(1976)The complexity of near-optimal graph coloring J. ACM 23 43-49

[9] Galbiati G.(1974)Approximation algorithms for combinatorial problems J. Comput. Syst. Sci. 9 256-278

[10] Maffioli F.(1994)Logical definability of NP optimization problems Inform. and Comput. 115 321-353