Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems

DOI10.1007/978-3-662-48350-3_25zbMath1466.90083OpenAlexW2281047077WikidataQ56976965 ScholiaQ56976965MaRDI QIDQ3452793

Fritz Bökler, Petra Mutzel

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_25

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)

Related Items

Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions, Analysis of the weighted Tchebycheff weight set decomposition for multiobjective discrete optimization problems, The vector linear program solver Bensolve -- notes on theoretical background, Combinatorial optimization with interaction costs: complexity and solvable cases, Finding multi-objective supported efficient spanning trees, An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem

Cites Work

• A dual variant of Benson's ``outer approximation algorithm for multiple objective linear programming
• Benson type algorithms for linear vector optimization and applications
• On generating all maximal independent sets
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An optimal convex hull algorithm in any fixed dimension
• A survey and annotated bibliography of multiobjective combinatorial optimization
• The upper bound theorem for polytopes: An easy proof of its asymptotic version
• A Recursive Algorithm for Finding All Nondominated Extreme Points in the Outcome Set of a Multiobjective Integer Programme
• An Exact Algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer Programs
• Geometric Duality in Multiple Objective Linear Programming
• Bicriteria Transportation Problem
• A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization
• Improved smoothed analysis of multiobjective optimization
• A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts