Due to the rising demand for Quality of Service (QoS) in the emerging network, this paper considers the routing problem of efficiently planning the transmission path of flow demands to balance the load of the network. Existing classical routing algorithms based on static decision-making are unable to adjust to dynamical scenarios with fluctuating flow. Traditional reinforcement learning-based methods face challenges in large-scale scenarios due to the vast state and action spaces. Besides, the neural networks used for policy generation also suffer from issues like rudimentary feature extraction and limited learning capability. In this paper, we first introduce RequestNet, a novel attention-based model designed to better leverage the information of network topology and feature correlations. We also propose a multi-agent modeling approach for the network packet routing problem, named RequestNet-MA, which treats pairs of edge routers as agents, allowing us to allocate traffic from the perspective of flow demands, thus significantly reducing the dimensions of state and action spaces and enhancing inter-agent communication and cooperation. Extensive experiments and ablation studies demonstrate that the proposed RequestNet-MA can reduce maximum link utilization and scale well to a large-scale network.

In this paper, we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem, where the cost function is additive linear, and the cover function is non-monotone approximately submodular. We study the problem under streaming model and propose three bicriteria approximation algorithms. Firstly, we provide an intuitive streaming algorithm under the assumption of known optimal objective value. The intuitive streaming algorithm returns a solution such that its cover function value is no less than $\alpha \mathsf{}\mathrm{(}\mathrm{1}\mathrm{-}ϵ\mathrm{)}$ times threshold, and the cost function is no more than ${\mathrm{(}\mathrm{2}\mathrm{+}ϵ\mathrm{)}}^{\mathrm{2}}\mathrm{/}\mathrm{(}{ϵ}^{\mathrm{2}}\mathsf{}{\omega }^{\mathrm{2}}\mathrm{)}\mathrm{\cdot }\kappa$, where $\kappa$ is a value that we suppose for the optimal solution and $\alpha$ is the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly. Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance, and maintain the same bicriteria approximation ratio. Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio. Additionally, we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.