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, e.g., 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 $\alpha$, then a lexicographically maximal solution achieves $(\alpha/2)$-approximation, and this bound is tight.
翻译:我们研究加权比对和机器人交叉问题的地名录最大解决办法有多好。 如果需要尽可能多的重元素,那么这个解决办法就最大了。如果需要尽可能多的重元素,如果这样的话,它需要尽可能多的第二大元素,等等。如果不同的重量值足够分散,例如,两个不同重量值的最低比至少是地面设定的大小,那么这两个不同重量值的最低比至少是地面设定的大小,那么,地名录最大度和通常的加权最佳度是相等的。我们表明,这种等值维持的门槛是完全的$2。此外,我们证明,如果比小于2美元,比如说$\alpha$,那么一个地名录上的最大解决办法就是$(alpha/2)-accessionation),而这个界限是紧凑的。