Assessment of approximate algorithms: The error measure's crucial role (Q1820671)

Initially, the distinction between exact and approximate algorithms is accounted for. We then consider a broad class of decision problems including the so-called account location or k-plant location problem (kPLP), and show that the choice of an appropriate reference value is critical; even an apparent plausible choice may lead to disputable conclusions. A family of data instances for kPLP is presented for which the relative duality gap approaches one. Consequently, for this class of optimization problems, no error measure on the upper bound should permit a characterization of the strong linear programming relaxation as ''good''.