惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

L
LangChain Blog
酷 壳 – CoolShell
酷 壳 – CoolShell
雷峰网
雷峰网
量子位
V
V2EX
S
SegmentFault 最新的问题
月光博客
月光博客
博客园 - 【当耐特】
Hugging Face - Blog
Hugging Face - Blog
V
Visual Studio Blog
大猫的无限游戏
大猫的无限游戏
T
Tailwind CSS Blog
博客园_首页
博客园 - Franky
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
美团技术团队
Y
Y Combinator Blog
The Cloudflare Blog
C
Check Point Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
腾讯CDC
B
Blog
Stack Overflow Blog
Stack Overflow Blog
P
Proofpoint News Feed

cs updates on arXiv.org

Beyond Binary Edits Robust Multimodal Knowledge Editing with Adversarial Subspace Alignment Agentic Proving for Program Verification MemAudit: Post-hoc Auditing of Poisoned Agent Memory via Causal Attribution and Structural Anomaly Detection OpenSkillEval: Automatically Auditing the Open Skill Ecosystem for LLM Agents One Policy, Infinite NPCs: Persona-Traceable Shared RL Policies for Scalable Game Agents How Human-Like Are Large Language Models? A Register-Aware Linguistic Evaluation Framework Benchmarking Google Embeddings 2 against Open-Source Models for Multilingual Dense Retrieval and RAG Systems Structure-Guided Entity Resolution: Fine-Tuning LLMs for Robust Name Matching in Complex Linguistic Contexts Solving the Aircraft Disassembly Scheduling Problem Co-ReAct: Rubrics as Step-Level Collaborators for ReAct Agents CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem Asking For An Old Friend: Diagnosing and Mitigating Temporal Failure Modes in LLM-based Statutory Question Answering EDGE-OPD: Internalizing Privileged Context with Evidence Guided On-Policy Distillation ARES: Automated Rubric Synthesis for Scalable LLM Reinforcement Learning SSDAU: Structured Semantic Data Augmentation for Joint Entity and Relation Extraction Naturalistic measure of social norms alignment Articulatory strategy as a source of variation in acoustic vowel dynamics When Planning Fails Despite Correct Execution: On Epistemic Calibration for LLM-Based Multi-Agent Systems EquiSumm : A Gender Bias-Aware Framework for Inclusive Tweet Summarization Metacognition as Reward: Reinforcing LLM Reasoning via Knowledge and Regulation Signals From Correctness to Preference: A Framework for Personalized Agentic Reinforcement Learning Cultural Adaptation in Large Language Models for Political Discourse Emotion Recognition in Sign Language Conversation ClimateChat-300K: A Multi-Modal Facebook Dataset for Understanding Diverse Perspectives in Climate Communication AraHopeCorpus: Annotation Guidelines and Dataset for Hope Speech in Arabic Social Media Crisis Discourse Human-in-the-Loop Multi-Agent Ventilator Decision Support with Contextual Bandit Preference Learning Convergence Without Understanding: When Language Models Agree on Representations but Disagree on Reasoning DART: Semantic Recoverability for Structured Tool Agents Ontological Knowledge Blocks: Executable Compliance and Profile-Based Validation for Trustworthy AI Systems Parallel Context Compaction for Long-Horizon LLM Agent Serving
Approximation algorithms for the prize-collecting rural p...
Hong Li, Jianping Li, Wei Li, Runtao Xie, Xiaoxiao Yang · 2026-05-24 · via cs updates on arXiv.org

In this paper, we study the prize-collecting rural postman problem (PCRPP), a variant of the rural postman problem. Given a PCRPP instance consisting of an undirected graph whose edges have nonnegative lengths and nonnegative profits, together with a root vertex, the goal is to find a closed walk that starts and ends at the root vertex and minimizes the sum of its length and the profits of all edges that the walk does not traverse. A natural way to design an approximation algorithm for the PCRPP is to construct a prize-collecting traveling salesman problem (PCTSP) instance from the given PCRPP instance, apply an approximation algorithm to the PCTSP instance, and then convert the resulting PCTSP solution into a PCRPP solution. We show that this approach has an inherent factor-two barrier: even if the constructed PCTSP instance is solved exactly, the resulting PCRPP solution can have objective value arbitrarily close to twice the optimum value of the original PCRPP instance. Our main result is a polynomial-time approximation algorithm with approximation ratio strictly smaller than 1.6 for the PCRPP. On a public 118-instance benchmark set, the proposed algorithm has average and maximum optimality gaps of 3.39\% and 12.12\%, respectively.