Two linear programming algorithms for the linear discrete norm problem
Authors:
Ronald D. Armstrong and James P. Godfrey
Journal:
Math. Comp. 33 (1979), 289300
MSC:
Primary 90C05
MathSciNet review:
0525398
Fulltext 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 , 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
0388750 (52 #9584)
 [2]
Nabih
N. Abdelmalek, An efficient method for the discrete
linear 𝐿₁ approximation problem, Math. Comp. 29 (1975), 844–850. MR 0378354
(51 #14522), http://dx.doi.org/10.1090/S00255718197503783548
 [3]
R. D. ARMSTRONG & E. L. FROME, "Least absolute value estimators for oneway and twoway 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 0438660
(55 #11568)
 [5]
I.
Barrodale and F.
D. K. Roberts, An improved algorithm for discrete 𝑙₁
linear approximation, SIAM J. Numer. Anal. 10 (1973),
839–848. MR 0339449
(49 #4208)
 [6]
A.
Charnes, Optimality and degeneracy in linear programming,
Econometrica 20 (1952), 160–170. MR 0056264
(15,48d)
 [7]
A.
Charnes and W.
W. Cooper, Management models and industrial applications of linear
programming. Vol. II, John Wiley & Sons, Inc., New YorkLondon,
1961. MR
0157774 (28 #1003b)
 [8]
A.
Charnes and W.
W. Cooper, Optimal estimation of executive compensation by linear
programming, Management Sci. 1 (1955), 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, AddisonWesley Series in
Industrial Management, AddisonWesley Publishing Co., Inc., Reading,
Mass.London, 1962. MR 0135622
(24 #B1669)
 [11]
Otto
J. Karst, Linear curve fitting using least deviations, J.
Amer. Statist. Assoc. 53 (1958), 118–132. MR 0134453
(24 #B506)
 [12]
G.
F. McCormick and V.
A. Sposito, Using the 𝐿₂estimator in
𝐿₁estimation, SIAM J. Numer. Anal. 13
(1976), no. 3, 337–343. MR 0448808
(56 #7113)
 [13]
Michel
Simonnard, Linear programming, Translated from the French by
William S. Jewell, PrenticeHall, Inc., Englewood Cliffs, N.J., 1966. MR 0201195
(34 #1079)
 [14]
Harvey
M. Wagner, The dual simplex algorithm for bounded variables,
Naval Res. Logist. Quart. 5 (1958), 257–261. MR 0101168
(20 #7590)
 [15]
Harvey
M. Wagner, Linear programming techniques for regression
analysis, J. Amer. Statist. Assoc. 54 (1959),
206–212. MR 0130753
(24 #A612)
 [1]
 N. N. ABDELMALEK, "On the discrete linear , approximation and , solutions of overdetermined linear equations," J. Approximation Theory, v. 11, 1974, pp. 3853. MR 0388750 (52:9584)
 [2]
 N. N. ABDELMALEK, "An efficient method for the discrete linear , approximation problem," Math. Comp., v. 29, 1975, pp. 844850. MR 0378354 (51:14522)
 [3]
 R. D. ARMSTRONG & E. L. FROME, "Least absolute value estimators for oneway and twoway 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. 555565. 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. 839848. MR 0339449 (49:4208)
 [6]
 A. CHARNES, "Optimality and degeneracy in linear programming," Econometrica, v. 20 (2), 1952, pp. 160170. 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. 138151. 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, AddisonWesley, 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. 118132. 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. 337343. MR 0448808 (56:7113)
 [13]
 M. SIMONNARD, Linear Programming, PrenticeHall, 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. 257261. MR 0101168 (20:7590)
 [15]
 H. M. WAGNER, "Linear programming techniques for regression analysis," J. Amer. Statist. Assoc., v. 54, 1959, pp. 206212. MR 0130753 (24:A612)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
90C05
Retrieve articles in all journals
with MSC:
90C05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197905253982
PII:
S 00255718(1979)05253982
Article copyright:
© Copyright 1979
American Mathematical Society
