Two linear programming algorithms for the linear discrete 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

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 , 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]**N. N. ABDELMALEK, "On the discrete linear , approximation and , solutions of overdetermined linear equations,"*J. Approximation Theory*, v. 11, 1974, pp. 38-53. MR**0388750 (52:9584)****[2]**N. N. ABDELMALEK, "An efficient method for the discrete linear , approximation problem,"*Math. Comp.*, v. 29, 1975, pp. 844-850. MR**0378354 (51:14522)****[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]**R. D. ARMSTRONG & J. W. HULTZ, "An algorithm for a restricted discrete approximation problem in the , norm,"*SIAM J. Numer. Anal.*, v. 14, 1977, pp. 555-565. MR**0438660 (55:11568)****[5]**I. BARRODALE & F. D. K. ROBERTS, "An improved algorithm for discrete linear approximation,"*SIAM J. Numer. Anal.*, v. 10, 1973, pp. 839-848. MR**0339449 (49:4208)****[6]**A. CHARNES, "Optimality and degeneracy in linear programming,"*Econometrica*, v. 20 (2), 1952, pp. 160-170. MR**0056264 (15:48d)****[7]**A. CHARNES & W. W. COOPER,*Management Models and Industrial Applications of Linear Programming*, Vol. II, Wiley, New York, 1961. MR**0157774 (28:1003b)****[8]**A. CHARNES, W. W. COOPER & R. FERGUSON, "Optimal estimation of executive compensation by linear programming,"*Management Sci.*, v. 2, 1955, pp. 138-151. MR**0073914 (17:507a)****[9]**J. GILSINN, K. HOFFMAN, R. H. F. JACKSON, E. LEYENDECKER, P. SAUNDERS & D. SHIER, "Methodology and analysis for comparing discrete linear approximation codes,"*Comm. Statist.*, v. B6(4), 1977.**[10]**G. HADLEY,*Linear Programming*, Addison-Wesley, Reading, Mass., 1962. MR**0135622 (24:B1669)****[11]**O. J. KARST, "Linear curve fitting using least deviations,"*J. Amer. Statist. Assoc.*, v. 53, 1958, pp. 118-132. MR**0134453 (24:B506)****[12]**G. F. McCORMICK & V. A. SPOSITO, "Using the -estimator in the -estimation,"*SIAM J. Numer. Anal.*, v. 13, 1976, pp. 337-343. MR**0448808 (56:7113)****[13]**M. SIMONNARD,*Linear Programming*, Prentice-Hall, Englewood Cliffs, N.J., 1966. MR**0201195 (34:1079)****[14]**H. M. WAGNER, "The dual simplex algorithm for bounded variables,"*Naval Res. Logist Quart.*, v. 5, 1958, pp. 257-261. MR**0101168 (20:7590)****[15]**H. M. WAGNER, "Linear programming techniques for regression analysis,"*J. Amer. Statist. Assoc.*, v. 54, 1959, pp. 206-212. MR**0130753 (24:A612)**

Retrieve articles in *Mathematics of Computation*
with MSC:
90C05

Retrieve articles in all journals with MSC: 90C05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1979-0525398-2

Article copyright:
© Copyright 1979
American Mathematical Society