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

DOI10.1007/BF01933708MaRDI QIDQ1820671zbMATH OpenFDO

Authors Jakob Krarup, Peter Mark Pruzan

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01933708

zbMATH Keywords

account locationapproximate algorithmsexact and approximate algorithmsk-plant locationworst-case analysis

Mathematics Subject Classification ID

Inventory, storage, reservoirs (90B05) Applications of mathematical programming (90C90)

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.

Recommendations

• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• scientific article; zbMATH DE number 3902037
• scientific article; zbMATH DE number 4037617
• scientific article; zbMATH DE number 3999286
• scientific article; zbMATH DE number 1202930

Cites work

• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Fractional vertices, cuts and facets of the simple plant location problem
• The simple plant location problem: Survey and synthesis
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(3)

• Improving and estimating the accuracy of Strassen's algorithm
• The simple plant location problem: Survey and synthesis
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems

This page was built for publication: Assessment of approximate algorithms: The error measure's crucial role

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820671)