Valuated matroid intersection .1. Optimality criteria
Valuated matroid intersection .1. Optimality criteria
复制标题
DOI：
10.1137/s0895480195279994
复制
发表时间：
1996-11-01
影响因子：
0.8
通讯作者：
Murota, K
中科院分区：
文献类型：
--
作者：
Murota, K
独立的分配问题（或加权矩阵交叉问题）是使用着装和Wenzel的矩阵估值扩展的，这些估值附加到基础两部分图的顶点集，作为额外的权重。具体而言，所考虑的问题如下：给定二分G =（v+，v-; a）具有重量W：A-> r和Matroid估值Omega（+）（+）和欧米茄（ - ）在V+和V-上，分别找到一个匹配的m（或等于a）最大化sigma {w（a）\ a是m} + omega（ +）的元素（部分）衍生物（+）m）+欧米茄（ - ）（部分导数（ - ）m），其中部分衍生物（+）m和部分衍生物（ - ）m表示V+和V-入射的顶点集。独立分配问题的先前结果的扩展，建立了两个最佳标准：一个在辅助图中的负循环方面，另一个是在电势方面。
The independent assignment problem (or the weighted matroid intersection problem) is extended using Dress and Wenzel's matroid valuations, which are attached to the vertex set of the underlying bipartite graph as an additional weighting. Specifically, the problem considered is as follows: given a bipartite graph G = (V+,V-;A) with are weight w : A --> R and matroid valuations omega(+) and omega(-) on V+ and V-, respectively, find a matching M(subset of or equal to A) that maximizes Sigma{w(a) \ a is an element of M} + omega(+)(partial derivative(+) M) + omega(-)(partial derivative(-) M), where partial derivative(+) M and partial derivative(-) M denote the sets of vertices in V+ and V- incident to M. As natural extensions of the previous results for the independent assignment problem, two optimality criteria are established: one in terms of potentials and the other in terms of negative cycles in an auxiliary graph.