Reductions, completeness and the hardness of approximability

Reductions, completeness and the hardness of approximability

0.00 Avg rating0 Votes
Article ID: iaor20084040
Country: Netherlands
Volume: 172
Issue: 3
Start Page Number: 719
End Page Number: 739
Publication Date: Aug 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

In computability and in complexity theory reductions are widely used for mapping sets into sets in order to prove undecidability or hardness results. In the study of the approximate solvability of hard discrete optimization problems, suitable kinds of reductions, called approximation preserving reductions, can also be used to transfer from one problem to another either positive results (solution techniques) or negative results (non-approximability results). In this paper various kinds of approximation preserving reductions are surveyed and their properties discussed. The role of completeness under approximation preserving reductions is also analyzed and its relationship with hardness of approximability is explained.

Reviews

Required fields are marked *. Your email address will not be published.