Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong, Hyundong Shin
Sweep coverage requires each point of interest (PoI) to be revisited by some mobile sensor at least once during every sweep period, and it underlies persistent patrolling, environmental monitoring, and infrastructure inspection. Given a set of $N$ PoIs, each associated with a nonnegative weight representing its importance, the weighted budgeted sweep coverage problem (WB-SCP) seeks routing trajectories for a budget of $M\leq N$ identical mobile sensors with a common maximum speed to maximize the total weight of the sweep-covered PoIs. For the unweighted special case in which every PoI has unit weight, the first constant-factor approximation algorithm achieves a ratio of $0.0116-O(\varepsilon)$ for any constant $\varepsilon>0$, and whether the WB-SCP itself admits such an algorithm has remained open. In this paper, we resolve this open question by proposing two constant-factor approximation algorithms for the WB-SCP. The first converts any bifactor $(α,β)$-approximation algorithm into a $β/(2α)$-approximation algorithm, yielding a ratio of $1/16=0.0625$. The second builds on a greedy maximum-coverage framework and improves the ratio to $1-e^{-1/2}-\varepsilon$ for any fixed $\varepsilon>0$. Both algorithms also improve the best-known ratio for the unweighted case, and the second extends to heterogeneous sensors with different speeds while preserving the same guarantee.
Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong, Hyundong Shin
The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices, where edge costs satisfy the triangle inequality. The biased TSP (BTSP) is a natural generalization of the metric TSP, in which the vertex set is partitioned into $k$ subsets: edge costs satisfy the triangle inequality within each subset, while edges crossing the subsets may violate the triangle inequality by a certain bias factor. This model captures scenarios in which distances are metric only locally but may be distorted across different regions or types of vertices. In this paper, we study approximation algorithms for the BTSP and its path variant, the biased traveling salesman path problem (BTSPP), which asks for a minimum-cost Hamiltonian path. Previously, constant-factor approximation algorithms were known only for the case $k=2$. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer $k>2$ has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit $O(k)$-approximation algorithms with running time $N^{O(2^k k!)}$. Moreover, for the BTSPP with $k=2$, we propose an improved $(α+2+\varepsilon)$-approximation algorithm, where $α<3/2-10^{-34}$ is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of $4$
Jiaquan Zhang, Chaoning Zhang University of Electronic Science and Technology of China, Shuxu Chen, Zhenzhen Huang, Pengcheng Zheng, Zhicheng Wang, Ping Guo Hong Kong Yuwin Technology Co., Ltd., Fan Mo University of Electronic Science and Technology of China 等 12 位作者
Although LLM agents can leverage tools for complex tasks, they still need memory to maintain cross-turn consistency and accumulate reusable information in long-horizon interactions. However, retrieval-based external memory systems incur low online overhead but suffer from unstable accuracy due to limited query construction and candidate filtering. In contrast, many systems use repeated large-model calls for online memory operations, improving accuracy but accumulating latency over long interactions. We propose LightMem, a lightweight memory system for better agent memory driven by Small Language Models (SLMs). LightMem modularizes memory retrieval, writing, and long-term consolidation, and separates online processing from offline consolidation to enable efficient memory invocation under bounded compute. We organize memory into short-term memory (STM) for immediate conversational context, mid-term memory (MTM) for reusable interaction summaries, and long-term memory (LTM) for consolidated knowledge, and uses user identifiers to support independent retrieval and incremental maintenance in multi-user settings. Online, LightMem operates under a fixed retrieval budget and selects memories via a two-stage procedure: vector-based coarse retrieval followed by semantic consistency re-ranking. Offline, it abstracts reusable interaction evidence and incrementally integrates it into LTM. Experiments show consistent gains across model scales, with an average F1 improvement of about 2.5 over A-MEM on LoCoMo, while achieving higher efficiency and low median latency (83 ms for retrieval and 581 ms end-to-end).
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表