Approximation by lexicographically maximal solutions in matching and matroid intersection problems
Approximation by lexicographically maximal solutions in matching and matroid intersection problems
复制标题
匹配和拟阵相交问题中字典序最大解的近似
DOI：
10.1016/j.tcs.2022.01.035
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Yu Yokoi
中科院分区：
文献类型：
--
作者：
Kristof Berczi;Tamas Kiraly;Yutaro Yamaguchi;Yu Yokoi
我们研究了字典序最大解在加权匹配和拟阵交集问题中的优劣。如果一个解决方案使用尽可能多的最重元素，那么它在词典顺序上是最大的，在此情况下，它使用尽可能多的第二重元素，依此类推。如果不同的权值是充分分散的，例如，两个不同的权值的最小比率至少是基本集合大小，则词典编目最大值和通常的加权最优性是等价的。我们证明了这个等价成立的比率的阈值恰好是2。此外，我们还证明了如果这个比率小于2，比如α，则字典序最大解达到(α/2)-逼近，并且这个界是紧的。
We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many heaviest elements as possible, and subject to this, it takes as many second heaviest elements as possible, and so on. If the distinct weight values are sufficiently dispersed, eg, the minimum ratio of two distinct weight values is at least the ground set size, then the lexicographical maximality and the usual weighted optimality are equivalent. We show that the threshold of the ratio for this equivalence to hold is exactly 2. Furthermore, we prove that if the ratio is less than 2, say α, then a lexicographically maximal solution achieves (α/2)-approximation, and this bound is tight.