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

On generalized balanced optimization problems

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

In the generalized balanced optimization problem (GBaOP) the objective value \({\max_{e \in S}{|c(e)-k\max(S)|}}\) is minimized over all feasible subsets S of E = {1, . . . , m}. We show that the algorithm proposed in Punnen and Aneja (Oper Res Lett 32:27–30, 2004) can be modified to ensure that the resulting solution is indeed optimal. This modification is attained at the expense of increased worst-case complexity, but still maintains polynomial solvability of various special cases that are of general interest. In particular, we show that GBaOP can be solved in polynomial time if an associated bottleneck problem can be solved in polynomial time. For the solution of this bottleneck problem, we propose two alternative approaches.

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

  • Berman O, Einav D, Handler G (1990) The constrained bottleneck problem in networks. Oper Res 38: 178–181

    Article  MATH  MathSciNet  Google Scholar 

  • Błażewicz J, Formanowicz P, Kasprzak M, Schuurman P, Woeginger GJ (2007) A polynomial time equivalence between DNA sequencing and the exact perfect matching problem. Discrete Optim 4: 154–162

    Article  MATH  MathSciNet  Google Scholar 

  • Camerini PM, Hamacher HW (1989) Intersection of two matroids: (condensed) border graphs and ranking. SIAM J Discrete Math 2: 16–27

    Article  MATH  MathSciNet  Google Scholar 

  • Deǐneko VG, Woeginger GJ (2006) On the robust assignment problem under a fixed number of cost scenarios. Oper Res Lett 34: 175–179

    Article  MathSciNet  Google Scholar 

  • Edmonds J, Fulkerson DR (1970) Bottleneck extrema. J Combin Theory 8: 299–306

    Article  MATH  MathSciNet  Google Scholar 

  • Gorski J, Ruzika S (2009) On k-max-optimization. Oper Res Lett 37: 23–26

    Article  MATH  MathSciNet  Google Scholar 

  • Hamacher HW, Rendl F (1991) Color constrained combinatorial optimization problems. Oper Res Lett 10: 211–219

    Article  MATH  MathSciNet  Google Scholar 

  • Karzanov AV (1987) Maximum matching of given weight in complete and complete bipartite graphs. Cybern Syst Anal 23: 8–13

    Article  MATH  Google Scholar 

  • Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin

    MATH  Google Scholar 

  • Lawler EL (2001) Combinatorial optimization: networks and matroids. Dover Publications, Mineola

    MATH  Google Scholar 

  • Leclerc M (1988–1989) Optimizing over a slice of the bipartite matching polytope. Discrete Math 73: 159–162

    Article  MathSciNet  Google Scholar 

  • Lee J (1992) On constrained bottleneck extrema. Oper Res 40: 813–814

    Article  MATH  MathSciNet  Google Scholar 

  • Martello S, Pulleyblank WR, Toth P, de Werra D (1984) Balanced optimization problems. Oper Res Lett 3: 275–278

    Article  MATH  MathSciNet  Google Scholar 

  • Punnen AP, Aneja YP (2004) Lexicographic balanced optimization problems. Oper Res Lett 32: 27–30

    Article  MATH  MathSciNet  Google Scholar 

  • Ţigan Ş, Iacob EM, Stancu-Minasian IM (2005) Monotonic balanced optimization problem. Ann Tiberiu Popoviciu Seminar Funct Equ Approx Convex 3: 183–197

    Google Scholar 

  • Ţigan Ş, Stancu-Minasian IM, Coman I, Iacob ME (2008) On some stochastic balanced optimization problems. Ann Tiberiu Popoviciu Seminar Funct Equ Approx Convex 6: 105–127

    MATH  Google Scholar 

  • Turner L (2011) Universal combinatorial optimization problems. PhD thesis, Technical University of Kaiserslautern (to appear)

  • Yi T, Murty KG, Spera C (2002) Matchings in colored bipartite networks. Discrete Appl Math 121: 261–277

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Technical University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany

    Lara Turner & Horst W. Hamacher

  2. Department of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, Surrey, BC, V3T 0A3, Canada

    Abraham P. Punnen

  3. Odette School of Business, University of Windsor, Windsor, ON, N9B 3P4, Canada

    Yash P. Aneja

Authors
  1. Lara Turner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abraham P. Punnen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yash P. Aneja
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Horst W. Hamacher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lara Turner.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Turner, L., Punnen, A.P., Aneja, Y.P. et al. On generalized balanced optimization problems. Math Meth Oper Res 73, 19–27 (2011). https://doi.org/10.1007/s00186-010-0331-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-010-0331-4

Keywords

Search

Navigation