Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A general approximation method for bicriteria minimization problems
Halffmann P., Ruzika S., Thielen C., Willems D. Theoretical Computer Science695  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?
yes
no
Other reviews under "Optimization": Date
A general-purpose global optimizer: implementation and applications
Pronzato L., Walter E., Venot A., Lebruchec J. Mathematics and Computers in Simulation XXVI(5): 412-422, 1984. Type: Article
Jul 1 1985
Minkowski matrices.
Cryer C. ACM Transactions on Mathematical Software 9(2): 199-214, 1983. Type: Article
Feb 1 1985
Numerical optimization techniques
Evtushenko Y., Springer-Verlag New York, Inc., New York, NY, 1985. Type: Book (9789780387909493)
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy