Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Best of 2016 Recommended by Editor Recommended by Reviewer Recommended by Reader
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
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
An efficient schedulability analysis for optimizing systems with adaptive mixed-criticality scheduling
Zhao Y., Zeng H.  Real-Time Systems 53(4): 467-525, 2017. Type: Article
Oct 16 2017
Wonderful solutions and habitual domains for challenging problems in changeable spaces: from theoretical framework to applications
Larbani M., Yu P.,  Springer International Publishing, New York, NY, 2016. 275 pp. Type: Book
May 26 2017
Handbook of genetic programming applications
Gandomi A., Alavi A., Ryan C.,  Springer International Publishing, New York, NY, 2015. 593 pp. Type: Book (978-3-319208-82-4)
Feb 23 2017

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