A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints

References

• Ahuja R. K., Orlin J. B. Routing and Scheduling Algorithms for ADART. (1996) . Working Paper, Sloan School of Management, MIT, Cambridge, MAGoogle Scholar
• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Ayer M., Brunk H. D., Ewing G. M., Reid W. T., Silverman E. An empirical distribution function for sampling with incomplete information. Ann. Math. Statist. (1955) 26:641–647Crossref, Google Scholar
• Barlow R. E., Bartholomew D. J., Bremner D. J., Brunk H. D.Statistical Inference Under Order Restrictions (1972) (Wiley, New York) Google Scholar
• Bazaraa M., Sherali H., Shetty C. M.Nonlinear Programming: Theory and Algorithms (1993) (John Wiley and Sons, New York) Google Scholar
• Bazaraa M., Chakravarti N. Active set algorithms for isotonic regression: a unifying framework. Math. Programming (1990) 47:425–439Crossref, Google Scholar
• Best M. J., Chakravarti N., Ubhaya V. A. Minimizing separable convex functions subject to simple chain constraints. SIAM J. Optim. (2000) 10:658–672Crossref, Google Scholar
• Best M. J., Tan R. Y. An O(n3 log n) strongly polynomial algorithm for an isotonic regression knapsack problem. J. Optim.Theory and Application (1993) 79:463–478Crossref, Google Scholar
• Brunk H. D. Maximum likelihood estimates of monotone parameters. Ann. Math. Statist. (1955) 26:607–616Crossref, Google Scholar
• Casady R. E., Cryer J. D. Monotone percentile regression. Comput. Statist. Data Anal. (1976) 5:399–406Google Scholar
• Chakravarti N. Isotonic median regression: A linear programming approach. Math. Oper. Res. (1989) 14:303–308Link, Google Scholar
• Chakravarti N. Isotonic median regression for orders representable by rooted trees. Naval Res. Logist. (1992) 39:591–611Google Scholar
• Dykstra R. L. An isotonic regression algorithm. J. Statist. Planning and Inference (1981) 5:355–363Crossref, Google Scholar
• Eddy W. F., Qian S., Sampson S. Isotonic probability modeling with multiple covariates. Comput. Sci. Statist. (1995) 27:500–505Google Scholar
• Francis R. L., White J. A.Facility Location and Layout (1976) (Addison-Wesley, Reading, MA) Google Scholar
• Gebhardt F. An algorithm for monotone regression with one or more independent variables. Biometrika (1970) 57:263–271Crossref, Google Scholar
• Goldstein A. J., Kruskal J. B. Least-square fitting by monotonic functions having integer values. J. Amer. Statist. Assoc. (1976) 71:370–373Crossref, Google Scholar
• Kaufman Y., Tamir A. Locating service centers with precedence constraints. Discrete Appl. Math. (1993) 47:251–261Crossref, Google Scholar
• Lee C. I. C. The min-max algorithm and isotonic regression. Ann. Statist. (1983) 11:467–477Crossref, Google Scholar
• Liu M. H., Ubhaya V. A. Integer isotone optimization. SIAM J. Optimiz. (1997) 7:1152–1159Crossref, Google Scholar
• Maxwell W. L., Muchstadt J. A. Establishing consistent and realistic reorder intervals in production-distribution systems. Oper. Res. (1983) 33:1316–1341Link, Google Scholar
• Menendez J. A., Salvador B. An algorithm for isotonic median regression. Comput. Statist. and Data Anal. (1987) 5:399–406Crossref, Google Scholar
• Pardalos P. M., Xue G. L. Algorithms for a class of isotonic regression problems. Algorithmica (1999) 23:211–222Crossref, Google Scholar
• Pardalos P. M., Xue G. L., Li Y. Efficient computation of isotonic median regression. Appl. Math. Lett. (1995) 8:67–70Crossref, Google Scholar
• Restrepo A., Bovik A. C. Locally monotonic regression. IEEE Trans. Signal Processing (1994) 41:2796–2780Crossref, Google Scholar
• Robertson T., Waltman P. On estimating monotone parameters. Ann. Math. Statist. (1968) 39:1030–1039Crossref, Google Scholar
• Robertson T., Waltman P., Wright F. T. Multiple isotonic median regression. Ann. Statist. (1973) 1:422–432Crossref, Google Scholar
• Robertson T., Waltman P. Algorithms in order restricted statistical inference and the Cauchy mean property value. Ann. Statist. (1980) 8:645–651Crossref, Google Scholar
• Robertson T., Waltman P., Dykstra R. L.Order Restricted Statistical Inference (1988) (John Wiley and Sons, New York) Google Scholar
• Roundy R. A 98% effective lot-sizing rule for a multi-product multistage production/inventory system. Math. Oper. Res. (1986) 11:699–727Link, Google Scholar
• Schell M. J., Singh B. The reduced monotonic regression method. J. Amer. Statist. Assoc. (1997) 92:128–135Crossref, Google Scholar
• Shi N.-Z. The minimal L1 isotonic regression. Communications in Statist. (1995) 24:175Crossref, Google Scholar
• Stromberg U. An algorithm for isotonic regression with arbitrary convex distance function. Comput. Statist. and Data Anal. (1991) 11:205–219Crossref, Google Scholar
• Tamir A. The least element property of center location on tree networks with applications to distance and precedence constrained problems. Math. Programming (1993) 62:475–496Crossref, Google Scholar
• Ubhaya V. An O(n) algorithm for discrete n-point convex approximation with application to continuous case. J. Math. Anal. and Applications (1979) 72:338–354Crossref, Google Scholar
• Ubhaya V. An O(n) algorithm for least squares quasi-convex approximation. Comput. Math. Applications (1987) 14:583–590Crossref, Google Scholar
• Ubhaya V. A. Isotone optimization I. J. Approximation Theory (1974a) 12:146–159Crossref, Google Scholar
• Ubhaya V. A. Isotone optimization II. J. Approximation Theory (1974b) 12:315–342Crossref, Google Scholar