A general approximation method for bicriteria minimization problems

DOI10.1016/J.TCS.2017.07.003MaRDI QIDQ2402670zbMATH OpenOpenAlexFDO

Authors Pascal Halffmann, Stefan Ruzika, Clemens Thielen, David Willems

Publication date 13 September 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.02989

zbMATH Keywords

multicriteria optimizationapproximate Pareto curvebicriteria approximation algorithm

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given $0<epsilonleq1$ and a polynomial-time $alpha$-approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria $(alphacdot(1+2epsilon),alphacdot(1+frac2epsilon))$-approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in $frac1epsilon$. Moreover, we show that our method can be extended to compute an $(alphacdot(1+2epsilon),alphacdot(1+frac2epsilon))$-approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is $extsfNP$-hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless $extsfP=extsfNP$.

Recommendations

• Strongly polynomial-time approximation for a class of bicriteria problems.
• Small approximate Pareto sets for biobjective shortest paths and other problems
• Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
• Algorithms and Computation
• Decision-making based on approximate and smoothed Pareto curves

Cites work

• scientific article; zbMATH DE number 1002204 (Why is no real title available?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A Faster Deterministic Maximum Flow Algorithm
• A linear-time approximation algorithm for the weighted vertex cover problem
• A simple efficient approximation scheme for the restricted shortest path problem
• An improved FPTAS for Restricted Shortest Path.
• An improved LP-based approximation for Steiner tree
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximability and Hardness in Multi-objective Optimization
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• Combinatorial Optimization with Rational Objective Functions
• Efficiently computing succinct trade-off curves
• Faster parametric shortest path and minimum‐balance algorithms
• Max flows in \(O(nm)\) time, or better
• Multicriteria Optimization
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
• On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Small approximate Pareto sets for biobjective shortest paths and other problems

Cited in

(13)

• Norm-based approximation in bicriteria programming
• Strongly polynomial-time approximation for a class of bicriteria problems.
• The power of the weighted sum scalarization for approximating multiobjective optimization problems
• Approximations of bi-criteria optimization problem
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Reference point approximation method for the solution of bicriterial nonlinear optimization problems
• Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory
• Efficiency and approachability of nonconvex bicriteria programs
• Approximations of objective functions and constraints in bi-criteria optimization problems
• An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems
• Bi-criteria path problem with minimum length and maximum survival probability
• Approximating biobjective minimization problems using general ordering cones
• On Multivariate Discrete Moment Problems: Generalization of the Bivariate Min Algorithm for Higher Dimensions

This page was built for publication: A general approximation method for bicriteria minimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402670)