We propose a dense object detector with an instance-wise sampling strategy, named IQDet. Instead of using human prior sampling strategies, we first extract the regional feature of each ground-truth to estimate the instance-wise quality distribution.
According to a mixture model in spatial dimensions, the distribution is more noise-robust and adapted to the semantic pattern of each instance. Based on the distribution, we propose a quality sampling strategy, which automatically selects training samples in a probabilistic manner and trains with more high-quality samples. Extensive experiments on MS COCO show that our method steadily improves baseline by nearly 2.4 AP without bells and whistles. Moreover, our best model achieves 51.6 AP, outperforming all existing state-of-the-art one-stage detectors and it is completely cost-free in inference time.
Dense object detectors rely on the sliding-window paradigm that predicts the object over a regular grid of image. Meanwhile, the feature maps on the point of the grid are adopted to generate the bounding box predictions. The point feature is convenie
nt to use but may lack the explicit border information for accurate localization. In this paper, We propose a simple and efficient operator called Border-Align to extract border features from the extreme point of the border to enhance the point feature. Based on the BorderAlign, we design a novel detection architecture called BorderDet, which explicitly exploits the border information for stronger classification and more accurate localization. With ResNet-50 backbone, our method improves single-stage detector FCOS by 2.8 AP gains (38.6 v.s. 41.4). With the ResNeXt-101-DCN backbone, our BorderDet obtains 50.3 AP, outperforming the existing state-of-the-art approaches. The code is available at (https://github.com/Megvii-BaseDetection/BorderDet).
Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most $4$. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been
devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a $(6 + delta)$-approximation algorithm where $delta$ can be any positive constant, and there is still a gap of roughly $2$. In this paper, we narrow the gap significantly by proposing a $(4+delta)$-approximation algorithm where $delta$ can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is $mathit{poly}(m,n)cdot n^{mathit{poly}(frac{1}{delta})}$ where $n$ is the number of players and $m$ is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to $3 + frac{21}{26} approx 3.808$.
The max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. Each player $p$ has a non-negative value $v_{pr}$ on resource $r$. In the restricted case, we have $v_{pr}i
n {v_r, 0}$. That is, a resource $r$ is worth value $v_r$ for the players who desire it and value 0 for the other players. In this paper, we consider the configuration LP, a linear programming relaxation for the restricted problem. The integrality gap of the configuration LP is at least $2$. Asadpour, Feige, and Saberi proved an upper bound of $4$. We improve the upper bound to $23/6$ using the dual of the configuration LP. Since the configuration LP can be solved to any desired accuracy $delta$ in polynomial time, our result leads to a polynomial-time algorithm which estimates the optimal value within a factor of $23/6+delta$.
The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algo
rithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: roughly 4 for estimation and roughly $6 + 2sqrt{10}$ for construction. We propose an algorithm that constructs an allocation with value within a factor of $6 + delta$ from the optimum for any constant $delta > 0$. The running time is polynomial in the input size for any constant $delta$ chosen.
