This paper presents a new deterministic algorithm for the single-source shortest paths (SSSP) problem on real non-negative edge-weighted directed graphs, with running time O(m√{log n} + √{mnlog nlog log n}), which is O(m√{log nlog log n}) for sparse graphs. This improves the recent breakthrough result of O(m log^{2/3} n) time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].

We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS'96, SICOMP'00) gave a surprising randomized algorithm to verify associativity of an operation odot: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S.

Exploiting unmanned aerial vehicles (UAVs) to execute tasks is gaining growing popularity recently. To address the underlying task scheduling problem, conventional exact and heuristic algorithms encounter challenges such as rapidly increasing computation time and heavy reliance on domain knowledge, particularly when dealing with large-scale problems. The deep reinforcement learning (DRL) based methods that learn useful patterns from massive data demonstrate notable advantages. However, their decision space will become prohibitively huge as the problem scales up, thus deteriorating the computation efficiency. To alleviate this issue, we propose a double-level deep reinforcement learning (DL-DRL) approach based on a divide and conquer framework (DCF), where we decompose the task scheduling of multi-UAV into task allocation and route planning. Particularly, we design an encoder-decoder structured policy network in our upper-level DRL model to allocate the tasks to different UAVs, and we exploit another attention-based policy network in our lower-level DRL model to construct the route for each UAV, with the objective to maximize the total value of executed tasks given the maximum flight distance of the UAV. To effectively train the two models, we design an interactive training strategy (ITS), which includes pre-training, intensive training and alternate training. Experimental results show that our DL-DRL performs favorably against the learning-based and conventional baselines including the OR-Tools, in terms of solution quality and computation efficiency. We also verify the generalization performance of our approach by applying it to larger sizes of up to 1500 tasks and to different flight distances of UAVs. Moreover, we also show via an ablation study that our ITS can help achieve a balance between the performance and training efficiency. Our code is publicly available at https://faculty.csu.edu.cn/guohuawu/zh_CN/zdylm/193832/list/ index.htm.Note to Practitioners—Unmanned aerial vehicles (UAVs) are of great practical usage, as they have many real world applications. When a group of UAVs are employed to execute large-scale tasks, a core question is how to scheduling the UAVs, so that they could complete the tasks efficiently. However, it is a computationally hard problem due to the exponentially increasing search space. To solve this problem, we propose a double-level deep reinforcement learning (DL-DRL) approach within a divide-and-conquer framework (DCF), where the upper-level DRL model is responsible for the task allocation, and the lower-level DRL model is responsible for the UAV route planning. To better train the two DRL models who have interplay with each other, we propose a simple yet efficient training strategy, termed interactive training strategy (ITS), which includes pre-training, intensive training and alternate training. The experimental results based on instances of various scales show that our DL-DRL approach outperformed learning-based and conventional baselines, and the designed ITS could strike a good balance between performance and training efficiency. In light of those verified advantages, we believe that our DL-DRL approach has favorable potential to solve the practical task scheduling problem of multi-UAV in real world.

Knapsack is one of the most fundamental problems in theoretical computer science. In the (1 − є)-approximation setting, although there is a fine-grained lower bound of (n + 1 / є) 2 − o(1) based on the (min, +)-convolution hypothesis ([K'unnemann, Paturi and Stefan Schneider, ICALP 2017] and [Cygan, Mucha, Wegrzycki and Wlodarczyk, 2017]), the best algorithm is randomized and runs in Õ(n + (1/є)11/5/2Ω(√log(1/є))) time [Deng, Jin and Mao, SODA 2023], and it remains an important open problem whether an algorithm with a running time that matches the lower bound (up to a sub-polynomial factor) exists. We answer the question positively by showing a deterministic (1 − є)-approximation scheme for knapsack that runs in Õ(n + (1 / є) 2) time. We first extend a known lemma in a recursive way to reduce the problem to n є-additive approximation for n items with profits in [1, 2). Then we give a simple efficient geometry-based algorithm for the reduced problem.

The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems in theoretical computer science. It asks to compute the distance matrix of a given n-vertex graph. We revisit the classical problem of maintaining the distance matrix under a fully dynamic setting undergoing vertex insertions and deletions with a fast worst-case running time and efficient space usage. Although an algorithm with amortized update-time Õ(n 2) has been known for nearly two decades [Demetrescu and Italiano, STOC 2003], the current best algorithm for worst-case running time with efficient space usage runs is due to [Gutenberg and Wulff-Nilsen, SODA 2020], which improves the space usage of the previous algorithm due to [Abraham, Chechik, and Krinninger, SODA 2017] to Õ(n 2) but fails to improve their running time of Õ(n 2 + 2 / 3). It has been conjectured that no algorithm in O(n 2.5 − є) worst-case update time exists. For graphs without negative cycles, we meet this conjectured lower bound by introducing a Monte Carlo algorithm running in randomized Õ(n 2.5) time while keeping the Õ(n 2) space bound from the previous algorithm. Our breakthrough is made possible by the idea of “hop-dominant shortest paths,” which are shortest paths with a constraint on hops (number of vertices) that remain shortest after we relax the constraint by a constant factor.

Knapsack and Partition are two important additive problems whose fine-grained complexities in the (1 — ε)-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms.

Unbounded SubsetSum is a classical textbook problem: given integers w1,w2, …, wn∈[1,u], c,u, we need to find if there exists m1,m2, …, mn ∈ ℕ satisfying c =Σni=1 wimi. In its all-target version, t ∈ ℤ+ is given and the answers for all integers c ∈ [0, t] are required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. With new combinatorial insights into the structures of solutions, we present a novel two-phase approach. As a result, we show that: • All-Target CoinChange can be solved in Õ(u +t) time deterministically, improving the previous Õ(t4/3) time algorithm [Chan and He, ESA 2020]. • Residue Table can be solved in Õ(u) time deterministically, improving the previous Õ(u3/2) time algorithm [Klein, 2021]. •All-Target Unbounded Knapsack can be solved in Õ(T(u) + t) time, where is the running time for (min, +) convolution for length-n arrays, improving the previous O(u2 log u + t) time algorithm [Chan and He, ESA 2020].

The (unweighted) tree edit distance problem for$n$node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in$O(n^{3})$time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007]. The same paper also showed that$O(n^{3})$is the best possible running time for any algorithm using the so-called decomposition strategy, which underlies almost all the known algorithms for this problem. These algorithms would also work for the weighted tree edit distance problem, which cannot be solved in truly sub-cubic time under the APSP conjecture [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. In this paper, we break the cubic barrier by showing an$O(n^{2.9546})$time algorithm for the unweighted tree edit distance problem. We consider an equivalent maximization problem and use a dynamic programming scheme involving matrices with many special properties. By using a decomposition scheme as well as several combinatorial techniques, we reduce tree edit distance to the max-plus product of bounded-difference matrices, which can be solved in truly sub-cubic time [Bringmann, Grandoni, Saha, and Vassilevska Williams, FOCS 2016].