Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Duality for max-separable problems

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

In this paper we propose a general duality theory for a class of so called ‘max-separable’ optimization problems. In such problems functions h:R k → R of the form h(x 1, . . . , x k ) =  max j   h j (x j ), occur both as objective functions and as constraint functions (h j are assumed to be strictly increasing functions of one variable). As a result we obtain pairs of max-separable optimization problems, which possess both weak and strong duality property without a duality gap.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

  • Baccelli FL, Cohen G, Olsder GJ, Quadrat JP (1992) Synchronization and linearity, an algebra for discrete event systems. Wiley, Chichester

    Google Scholar 

  • Chadha SS, Chadha V (2007) Linear fractional programming and duality. CEJOR 15: 119–125

    Article  Google Scholar 

  • Cuninghame-Green RA (1979) Minimax algebra, Lecture notes in economics and mathematical systems, vol 166. Springer, Berlin

    Google Scholar 

  • Gavalec M, Zimmermann K (2010) Dual max-prod optimization problems. In: Proceedings of mathematical methods in economics, Part I, pp 168–176

  • Litvinov, GL, Maslov, VP, Sergeev , SN (eds) (2007) Idempotent and tropical mathematics and problems of mathematical Physics, vol I. Independent University, Moscow

    Google Scholar 

  • Maslov VP, Samborskij SN (1992) Idempotent analysis, advances in soviet mathematics, vol 13. AMS, Providence

  • Vorobjov NN (1967) Extremal algebra of positive matrices (in Russian). Datenverarbeitung und Kybernetik 3: 39–71

    Google Scholar 

  • Zhang Q (2008) Uniform LP duality for semi-definite and Semi-infinite programming. CEJOR 16: 205–213

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Hradec Králové, Faculty of Informatics and Management, Rokitanského 62, 50003, Hradec Králové, Czech Republic

    Martin Gavalec

  2. Charles University Prague, Faculty of Mathematics and Physics, Malostranské nám. 25, 11800, Praha 1, Czech Republic

    Karel Zimmermann

Authors
  1. Martin Gavalec
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Karel Zimmermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Gavalec.

Additional information

Under the support of GAČR # 402/09/0405 and MSM0021620838.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gavalec, M., Zimmermann, K. Duality for max-separable problems. Cent Eur J Oper Res 20, 409–419 (2012). https://doi.org/10.1007/s10100-011-0203-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-011-0203-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation