A general approximation method for bicriteria minimization problems

DOI10.1016/j.tcs.2017.07.003zbMath1418.90246arXiv1701.02989OpenAlexW2953286221MaRDI QIDQ2402670

Stefan Ruzika, David Willems, Pascal Halffmann, Clemens Thielen

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

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

Related Items (4)

Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Approximating biobjective minimization problems using general ordering cones ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ The power of the weighted sum scalarization for approximating multiobjective optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• An improved FPTAS for Restricted Shortest Path.
• Efficiently computing succinct trade-off curves
• An improved LP-based approximation for steiner tree
• Approximability and Hardness in Multi-objective Optimization
• Saving an epsilon
• Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• A linear-time approximation algorithm for the weighted vertex cover problem
• Bicriteria Network Design Problems
• A Faster Deterministic Maximum Flow Algorithm
• Multicriteria Optimization
• Max flows in O(nm) time, or better
• On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization
• Faster parametric shortest path and minimum‐balance algorithms
• A simple efficient approximation scheme for the restricted shortest path problem

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