Skip to main content
SpringerLink
Log in

NP-hardness of linear multiplicative programming and related problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aneja, Y.P., Aggarwal, V. and Nair, K.P.K. (1984), ‘On a class of quadratic programs’, European Journal of Operational Research 18, 62–70.

    Google Scholar 

  2. Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman.

  3. Karp, R.M. (1972), Reducibility among combinatorial problems. in Complexity of Computer Computations (R.E. Miller and J.W. Thatcher eds.), Plenum Press.

  4. Konno, H. and Kuno, T. (1990), Generalized linear multiplicative and fractional programming, Annals of Operations Research 25, 147–162.

    Google Scholar 

  5. Konno, H., Yajima, Y. and Matsui, T. (1991), Parametric simplex algorithms for solving a special class of nonconvex minimization problems, Journal of Global Optimization 1, 65–82.

    Google Scholar 

  6. Konno, H. and Kuno, T. (1992), Linear multiplicative programming, Mathematical Programming 56, 51–64.

    Google Scholar 

  7. Konno, H., Kuno, T. and Yajima, Y. (1992), Parametric simplex algorithms for a class of NP complete problems whose average number of steps are polynomial, Computational Optimization and Applications 1, 227–239.

    Google Scholar 

  8. Konno, H. and Kuno, T. (1995), Multiplicative programming problems, in Handbook of Global Optimization (R. Horst and P.M. Pardalos eds.), Kluwer Academic Publishers.

  9. Konno, H., Thach, P.T. and Tuy, H. Global Optimization: Low Rank Nonconvex Structures, Kluwer Academic Publishers (to appear).

  10. Kuno, T. and Konno, H. (1991), A parametric successive underestimation method for convex multiplicative programming problems, Journal of Global Optimization 1, 267–285.

    Google Scholar 

  11. Pardalos, P.M. (1990), Polynomial time algorithms for some classes of constrained nonconvex quadratic problems, Optimization 21, 843–853.

    Google Scholar 

  12. Pardalos, P.M. and Vavasis, S.A. (1991), Quadratic programming with one negative eigen-value is NP-hard, Journal of Global Optimization 1, 15–22.

    Google Scholar 

  13. Swarup, K. (1966). Indefinite quadratic programming, Cahiers du Centre d'Etudes de Recherche Operationnelle 8, 217–222.

    Google Scholar 

  14. Thoai, N.V. (1991), A global optimization approach for solving the convex multiplicative programming problem, Journal of Global Optimization 1, 341–357.

    Google Scholar 

  15. Tuy, H. and Tam, B.T. (1992), An efficient solution method for rank two quasiconcave minimization problems, Optimization 24, 43–56.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, 113, Tokyo, Japan

    T. Matsui

Authors
  1. T. Matsui
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Matsui, T. NP-hardness of linear multiplicative programming and related problems. J Glob Optim 9, 113–119 (1996). https://doi.org/10.1007/BF00121658

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00121658

Key words

Search

Navigation