Wei Zhang

Mingda Qiao, Wei Zhang

We study memory-bounded algorithms for the $k$-secretary problem. The algorithm of Kleinberg (SODA 2005) achieves an optimal competitive ratio of $1 - O(1/\sqrt{k})$, yet a straightforward implementation requires $Ω(k)$ memory. Our main result is a $k$-secretary algorithm that matches the optimal competitive ratio using $O(\log k)$ words of memory. We prove this result by establishing a general reduction from $k$-secretary to (random-order) quantile estimation, the problem of finding the $k$-th largest element in a stream. We show that a quantile estimation algorithm with an $O(k^α)$ expected error (in terms of the rank) gives a $(1 - O(1/k^{1-α}))$-competitive $k$-secretary algorithm with $O(1)$ extra words. We then introduce a new quantile estimation algorithm that achieves an $O(\sqrt{k})$ expected error bound using $O(\log k)$ memory. Of independent interest, we give a different algorithm that uses $O(\sqrt{k})$ words and finds the $k$-th largest element exactly with high probability, generalizing a result of Munro and Paterson (1980).

Xiao Wang, Yu Jin, Wentao Wu et al.

Object detection in event streams has emerged as a cutting-edge research area, demonstrating superior performance in low-light conditions, scenarios with motion blur, and rapid movements. Current detectors leverage spiking neural networks, Transformers, or convolutional neural networks as their core architectures, each with its own set of limitations including restricted performance, high computational overhead, or limited local receptive fields. This paper introduces a novel MoE (Mixture of Experts) heat conduction-based object detection algorithm that strikingly balances accuracy and computational efficiency. Initially, we employ a stem network for event data embedding, followed by processing through our innovative MoE-HCO blocks. Each block integrates various expert modules to mimic heat conduction within event streams. Subsequently, an IoU-based query selection module is utilized for efficient token extraction, which is then channeled into a detection head for the final object detection process. Furthermore, we are pleased to introduce EvDET200K, a novel benchmark dataset for event-based object detection. Captured with a high-definition Prophesee EVK4-HD event camera, this dataset encompasses 10 distinct categories, 200,000 bounding boxes, and 10,054 samples, each spanning 2 to 5 seconds. We also provide comprehensive results from over 15 state-of-the-art detectors, offering a solid foundation for future research and comparison. The source code of this paper will be released on: https://github.com/Event-AHU/OpenEvDET

Sen Li, Wei Zhang

This paper focuses on the coordination of a large population of dynamic agents with private information over multiple periods. Each agent maximizes the individual utility, while the coordinator determines the market rule to achieve group objectives. The coordination problem is formulated as a dynamic mechanism design problem. A mechanism is proposed based on the competitive equilibrium of the large population game. We derive the conditions for the general nonlinear dynamic systems under which the proposed mechanism is incentive compatible and can implement the social choice function in $ε$-Nash equilibrium. In addition, we show that for linear quadratic problems with bounded parameters, the proposed mechanism can maximize the social welfare subject to a total resource constraint in $ε$-dominant strategy equilibrium.