On matroids with multiple objectives
On matroids with multiple objectives
复制标题
在具有多个目标的拟阵上
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Ehrgott
中科院分区：
文献类型：
--
作者：
E. Ehrgott
在本文中，我们研究了具有多个目标函数的矩形的两个优化问题，即找到帕累托集和最大订购问题，这些问题是在找到基础中的圆锥形问题，使得最大的目标值是最小的。我们证明，这两个问题的决策版本都是NP库存的。提出了最高排序问题的解决方案过程，并给出了两个问题的解决方案集的结果。主要结果是通过基础交换属性对帕累托基群的表征，最后是适当的帕累托解决方案的连接结果。
In this paper we investigate two optimization problems for matroids with multiple objective functions, namely finding the pareto set and the max-ordering problem which conists in finding a basis such that the largest objective value is minimal. We prove that the decision versions of both problems are NP-complete. A solution procedure for the max-ordering problem is presented and a result on the relation of the solution sets of the two problems is given. The main results are a characterization of pareto bases by a basis exchange property and finally a connectivity result for proper pareto solutions.