Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
A general approximation method for bicriteria minimization problems
Halffmann P., Ruzika S., Thielen C., Willems D.  Theoretical Computer Science 695  1-15, 2017. Type: Article
Date Reviewed: Nov 9 2017

Many applications in operations research require the simultaneous optimization of multiple (typically mutually opposing) objective functions. Since the general problem is usually computationally intractable, bicriteria optimization restricts itself to two objectives while approximate optimization aims at solutions that differ from the optimal one by not more than a given factor.

This paper addresses a variant of approximate bicriteria optimization in which both objectives have lower and upper bounds, and it only seeks solutions for which the first objective does not exceed a given budget. It is shown how a polynomial-time approximate solution of the bicriteria problem can be obtained from any polynomial-time algorithm that approximately solves the problem of minimizing the weighted sum of both objective functions; this is achieved by solving finitely many instances of this single criterion problem. If the weighted sum optimization algorithm actually gives exact solutions, then the complexity of the method can be further improved by applying a bisection-style search in the solution space. However, the technique is restricted to minimization: unless P=NP, corresponding solutions for the maximization problem cannot be obtained in polynomial time.

The paper is self-contained: it presents all necessary mathematical background, the history of the problem, previously presented approaches, and how the new approach can be applied where previous ones have failed. Furthermore, it tabulates a list of concrete combinatorial optimization problems for which the new technique yields the best-known results. Further work will aim at generalizing the technique to more than two objectives and at applying other single-criteria algorithms.

Reviewer:  Wolfgang Schreiner Review #: CR145649 (1801-0015)
Bookmark and Share
  Editor Recommended
Featured Reviewer
Optimization (G.1.6 )
Approximation (G.1.2 )
Would you recommend this review?
Other reviews under "Optimization": Date
Nature-inspired algorithms and applied optimization
Yang X.,  Springer International Publishing, New York, NY, 2018. 330 pp. Type: Book (978-3-319676-68-5)
Sep 26 2018
Optimization and approximation
Pedregal P.,  Springer International Publishing, New York, NY, 2017. 254 pp. Type: Book (978-3-319648-42-2)
Feb 28 2018
Siarry P.,  Springer International Publishing, New York, NY, 2016. 489 pp. Type: Book (978-3-319454-01-6)
Jan 30 2018

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2018 ThinkLoud, Inc.
Terms of Use
| Privacy Policy