A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization |
| |
Authors: | Yoshio Okamoto Takeaki Uno |
| |
Institution: | 1. Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Ookayama 2–12–1–W8–88, Meguro-ku, Tokyo 152-8552, Japan;2. National Institute of Informatics, Hitotsubashi 2–1–2, Chiyoda-ku, Tokyo 101-8430, Japan |
| |
Abstract: | We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems. |
| |
Keywords: | Combinatorial optimization Complexity theory Linear programming Multiple objective programming |
本文献已被 ScienceDirect 等数据库收录! |
|