A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization

DOI10.1007/978-3-540-77120-3_53MaRDI QIDQ5387795zbMATH OpenOpenAlexFDO

Authors Yoshio Okamoto, Takeaki Uno

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_53

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Multi-objective and goal programming (90C29)

Recommendations

• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
• Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
• A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON
• Pareto optima of multicriteria integer linear programs
• On spanning tree problems with multiple objectives

Cites work

• Generating all vertices of a polyhedron is hard
• Geometric algorithms and combinatorial optimization.
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 2102225 (Why is no real title available?)
• scientific article; zbMATH DE number 915988 (Why is no real title available?)
• Multicriteria Optimization
• On matroids with multiple objectives
• Reverse search for enumeration
• Stochastic Algorithms: Foundations and Applications

Cited in

(4)

• Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
• Counting and enumeration complexity with application to multicriteria scheduling
• Polynomial-delay enumeration algorithms in set systems
• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization

This page was built for publication: A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization

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