A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization
A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization
复制标题
多标准优化中枚举问题的多项式时滞多项式空间算法
DOI：
10.1016/j.ejor.2010.10.008
复制
发表时间：
2011
影响因子：
6.4
通讯作者：
Yoshio Okamoto and Takeaki Uno
中科院分区：
文献类型：
--
作者：
Yoshio Okamoto;Yota Otachi;Ryuhei Uehara;and Takeaki Uno;Kazushige Terui;Kazushige Terui;照井一成;Yoshio Okamoto and Takeaki Uno
本文提出了一个多项式时间延迟多项式空间算法来计算多目标最小生成树问题的所有有效极值解，而文献中只研究了双目标情况.该算法基于Avis和Fukuda的反向搜索框架。我们还表明，同样的技术可以应用于多标准版本的最小成本的基础问题（可能退化）子模块化系统。作为一个最终的推广，我们提出了一个算法来枚举所有有效的极端解决方案的多目标线性规划。当给定的线性规划不退化时，算法在多项式时间延迟和多项式空间中运行。据我们所知，他们是第一个多项式时间延迟和多项式空间算法的问题。
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.