IDEAS home Printed from https://ideas.repec.org/p/cwl/cwldpp/946.html
   My bibliography  Save this paper

The Generalized Basis Reduction Algorithm

Author

Listed:

Abstract

Let F(x) be a convex function defined in R^{n}), which is symmetric about the origin and homogeneous of degree 1, and let L be the lattice of integers Z^{n}. A definition of a reduced basis, b^{1},...,b^{n}, of the lattice with respect to the distance function F is presented, and we describe an algorithm which yields a reduced basis in polynomial time, for fixed n. In the special case in which the bodies {x : F(x)

Suggested Citation

  • Herbert E. Scarf & Laszlo Lovasz, 1990. "The Generalized Basis Reduction Algorithm," Cowles Foundation Discussion Papers 946, Cowles Foundation for Research in Economics, Yale University.
  • Handle: RePEc:cwl:cwldpp:946 Note: CFP 818.
    as

    Download full text from publisher

    File URL: http://cowles.yale.edu/sites/default/files/files/pub/d09/d0946.pdf
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Schwert, G. William, 1989. "Business cycles, financial crises, and stock volatility," Carnegie-Rochester Conference Series on Public Policy, Elsevier, vol. 31(1), pages 83-125, January.
    2. Joseph G. Haubrich & Andrew W. Lo, "undated". "The Sources and Nature of Long-Term Memory in the Business Cycle," Rodney L. White Center for Financial Research Working Papers 05-89, Wharton School Rodney L. White Center for Financial Research.
    3. Hall, Joyce A. & Brorsen, B. Wade & Irwin, Scott H., 1989. "The Distribution of Futures Prices: A Test of the Stable Paretian and Mixture of Normals Hypotheses," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 24(01), pages 105-116, March.
    4. Blattberg, Robert C & Gonedes, Nicholas J, 1974. "A Comparison of the Stable and Student Distributions as Statistical Models for Stock Prices," The Journal of Business, University of Chicago Press, vol. 47(2), pages 244-280, April.
    5. Donald W.K. Andrews, 1986. "On the Performance of Least Squares in Linear Regression with Undefined Error Means," Cowles Foundation Discussion Papers 798, Cowles Foundation for Research in Economics, Yale University.
    6. Avram, Florin & Taqqu, Murad S., 1989. "Probability bounds for M-Skorohod oscillations," Stochastic Processes and their Applications, Elsevier, vol. 33(1), pages 63-72, October.
    7. Phillips, P.C.B., 1990. "Time Series Regression With a Unit Root and Infinite-Variance Errors," Econometric Theory, Cambridge University Press, vol. 6(01), pages 44-62, March.
    8. Hamilton, James D, 1989. "A New Approach to the Economic Analysis of Nonstationary Time Series and the Business Cycle," Econometrica, Econometric Society, vol. 57(2), pages 357-384, March.
    9. Bollerslev, Tim, 1986. "Generalized autoregressive conditional heteroskedasticity," Journal of Econometrics, Elsevier, vol. 31(3), pages 307-327, April.
    10. Davis, Richard & Resnick, Sidney, 1985. "More limit theory for the sample correlation function of moving averages," Stochastic Processes and their Applications, Elsevier, vol. 20(2), pages 257-279, September.
    11. Newey, Whitney & West, Kenneth, 2014. "A simple, positive semi-definite, heteroscedasticity and autocorrelation consistent covariance matrix," Applied Econometrics, Publishing House "SINERGIA PRESS", pages 125-132.
    12. Akgiray, Vedat & Booth, G Geoffrey, 1988. "The Stable-Law Model of Stock Returns," Journal of Business & Economic Statistics, American Statistical Association, vol. 6(1), pages 51-57, January.
    13. Peter C.B. Phillips & Victor Solo, 1989. "Asymptotics for Linear Processes," Cowles Foundation Discussion Papers 932, Cowles Foundation for Research in Economics, Yale University.
    14. Hamilton, James D., 1988. "Rational-expectations econometric analysis of changes in regime : An investigation of the term structure of interest rates," Journal of Economic Dynamics and Control, Elsevier, vol. 12(2-3), pages 385-423.
    15. Peter C.B. Phillips & Vassilis A. Hajivassiliou, 1987. "Bimodal t-Ratios," Cowles Foundation Discussion Papers 842, Cowles Foundation for Research in Economics, Yale University.
    16. Ploberger, Werner & Kramer, Walter, 1986. "On studentizing a test for structural change," Economics Letters, Elsevier, vol. 20(4), pages 341-344.
    17. Engle, Robert F, 1982. "Autoregressive Conditional Heteroscedasticity with Estimates of the Variance of United Kingdom Inflation," Econometrica, Econometric Society, vol. 50(4), pages 987-1007, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Herbert Scarf, 1994. "The Allocation of Resources in the Presence of Indivisibilities," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 111-128, Fall.
    2. William Cook & Thomas Rutherford & Herbert E. Scarf & David Shallcross, 1993. "An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 5(2), pages 206-212, May.
    3. Sanjay Mehrotra & Zhifeng Li, 2011. "Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices," Journal of Global Optimization, Springer, vol. 49(4), pages 623-649, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cwl:cwldpp:946. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Regan). General contact details of provider: http://edirc.repec.org/data/cowleus.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.