Assessment of approximate algorithms: The error measure's crucial role
type: Item
instance of: scholarly article
title: Assessment of approximate algorithms: The error measure's crucial role
zbMATH Open document ID: 0614.90031
DOI: 10.1007/BF01933708
author: Jakob Krarup
author: Peter Mark Pruzan
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 90C90
zbMATH DE Number: 3995409
zbMATH Keywords: approximate algorithms
zbMATH Keywords: worst-case analysis
zbMATH Keywords: exact and approximate algorithms
zbMATH Keywords: account location
zbMATH Keywords: k-plant location
MaRDI profile type: Publication
cites work: Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
cites work: Worst-Case Analysis of Heuristic Algorithms
cites work: Fractional vertices, cuts and facets of the simple plant location problem
cites work: The simple plant location problem: Survey and synthesis
description: scientific article; zbMATH DE number 3995409