Two linear programming algorithms for the linear discrete 𝐿₁ norm problem

Armstrong, Ronald D.; Godfrey, James P.

doi:10.1090/S0025-5718-1979-0525398-2

Two linear programming algorithms for the linear discrete $L\sb{1}$ norm problem

Authors: Ronald D. Armstrong and James P. Godfrey
Journal: Math. Comp. 33 (1979), 289-300
MSC: Primary 90C05
DOI: https://doi.org/10.1090/S0025-5718-1979-0525398-2
MathSciNet review: 0525398
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Computational studies by several authors have indicated that linear programming is currently the most efficient procedure for obtaining ${L_1}$ , norm estimates for a discrete linear problem. However, there are several linear programming algorithms, and the "best" approach may depend on the problem's structure (e.g., sparsity, triangularity, stability). In this paper we shall compare two published simplex algorithms, one referred to as primal and the other referred to as dual, and show that they are conceptually equivalent.

[1] Nabih N. Abdelmalek, On the discrete linear 𝐿₁ approximation and 𝐿₁ solutions of overdetermined linear equations, J. Approximation Theory 11 (1974), 38–53. MR 388750, https://doi.org/10.1016/0021-9045(74)90037-9
[2] Nabih N. Abdelmalek, An efficient method for the discrete linear 𝐿₁ approximation problem, Math. Comp. 29 (1975), 844–850. MR 378354, https://doi.org/10.1090/S0025-5718-1975-0378354-8
[3] R. D. ARMSTRONG & E. L. FROME, "Least absolute value estimators for one-way and two-way tables," Naval Res. Logist. Quart. (To appear.)
[4] Ronald D. Armstrong and John W. Hultz, An algorithm for a restricted discrete approximation problem in the 𝐿₁ norm, SIAM J. Numer. Anal. 14 (1977), no. 3, 555–565. MR 438660, https://doi.org/10.1137/0714034
[5] I. Barrodale and F. D. K. Roberts, An improved algorithm for discrete 𝑙₁ linear approximation, SIAM J. Numer. Anal. 10 (1973), 839–848. MR 339449, https://doi.org/10.1137/0710069
[6] A. Charnes, Optimality and degeneracy in linear programming, Econometrica 20 (1952), 160–170. MR 56264, https://doi.org/10.2307/1907845
[7] A. Charnes and W. W. Cooper, Management models and industrial applications of linear programming, John Wiley & Sons, Inc., New York-London, 1961. MR 0157773
[8] A. Charnes and W. W. Cooper, Optimal estimation of executive compensation by linear programming, Management Sci. 1 (1955), 138–151. MR 73914, https://doi.org/10.1287/mnsc.1.2.138
[9] J. GILSINN, K. HOFFMAN, R. H. F. JACKSON, E. LEYENDECKER, P. SAUNDERS & D. SHIER, "Methodology and analysis for comparing discrete linear ${L_1}$ approximation codes," Comm. Statist., v. B6(4), 1977.
[10] G. Hadley, Linear programming, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR 0135622
[11] Otto J. Karst, Linear curve fitting using least deviations, J. Amer. Statist. Assoc. 53 (1958), 118–132. MR 134453
[12] G. F. McCormick and V. A. Sposito, Using the 𝐿₂-estimator in 𝐿₁-estimation, SIAM J. Numer. Anal. 13 (1976), no. 3, 337–343. MR 448808, https://doi.org/10.1137/0713030
[13] Michel Simonnard, Linear programming, Translated from the French by William S. Jewell, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR 0201195
[14] Harvey M. Wagner, The dual simplex algorithm for bounded variables, Naval Res. Logist. Quart. 5 (1958), 257–261. MR 101168, https://doi.org/10.1002/nav.3800050306
[15] Harvey M. Wagner, Linear programming techniques for regression analysis, J. Amer. Statist. Assoc. 54 (1959), 206–212. MR 130753