The assignment problem with nearly Monge arrays and incompatible partner indices
The assignment problem with nearly Monge arrays and incompatible partner indices
复制标题
近 Monge 数组和不兼容的伙伴索引的分配问题
DOI：
10.1016/j.dam.2016.04.019
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Weiß C
中科院分区：
文献类型：
--
作者：
Weiß C
本文研究了代价数组除∞项可能违反Monge性质外，其他项均满足Monge性质的d维分配问题。我们假设∞项是由不兼容的伙伴索引产生的，并且它们的数量由每个索引的上界λ限定。我们证明了对于固定的d和λ，问题可以在线性时间内解决，并且当d或λ是输入的一部分时，问题变得强np困难。
In this paper we study the d-dimensional assignment problem in which entries of the cost array satisfy the Monge property, except for∞-entries, which may violate it. We assume that the∞-entries are incurred by incompatible partner indices and their number is bounded by an upper bound λ for each index. We show that the problem can be solved in linear time for fixed d and λ, and it becomes strongly NP-hard if d or λ is part of the input.
登录
查看更多内容
影响因子：
1.1
作者：
H. Enomoto;Yoshiaki Oda;K. Ota
通讯作者：
K. Ota
平面图、二分图和分割图上的加权着色：复杂性和近似
影响因子：
1.1
作者：
D. Werra;M. Demange;B. Escoffier;J. Monnot;V. Paschos
通讯作者：
V. Paschos
影响因子：
1.1
作者：
W. Bein;P. Brucker;James K. Park;P. Pathak
通讯作者：
P. Pathak
加权着色：进一步的复杂性和近似性结果
影响因子：
0.5
作者：
B. Escoffier;J. Monnot;V. Paschos
通讯作者：
V. Paschos
极限哈密顿线
影响因子：
4.9
作者：
Fred Supnick
通讯作者：
Fred Supnick