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

推荐订阅源

C
Check Point Blog
美团技术团队
Jina AI
Jina AI
人人都是产品经理
人人都是产品经理
The Cloudflare Blog
V
Visual Studio Blog
Google DeepMind News
Google DeepMind News
Hugging Face - Blog
Hugging Face - Blog
云风的 BLOG
云风的 BLOG
有赞技术团队
有赞技术团队
T
The Blog of Author Tim Ferriss
WordPress大学
WordPress大学
月光博客
月光博客
宝玉的分享
宝玉的分享
小众软件
小众软件
MongoDB | Blog
MongoDB | Blog
Apple Machine Learning Research
Apple Machine Learning Research
A
About on SuperTechFans
J
Java Code Geeks
博客园_首页
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
N
Netflix TechBlog - Medium
Vercel News
Vercel News
博客园 - 聂微东

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Settling Weighted Token Swapping up to Algorithmic Barriers
Nicole Wein, Guanyu Tony Zhang · 2025-07-30 · via cs.DS updates on arXiv.org

We study the weighted token swapping problem, in which we are given a graph on $n$ vertices, $n$ weighted tokens, an initial assignment of one token to each vertex, and a final assignment of one token to each vertex. The goal is to find a minimum-cost sequence of swaps of adjacent tokens to reach the final assignment from the initial assignment, where the cost is the sum over all swaps of the sum of the weights of the two swapped tokens. Unweighted token swapping has been extensively studied: it is NP-hard to approximate to a factor better than $14/13$, and there is a polynomial-time 4-approximation, along with a tight "barrier" result showing that the class of locally optimal algorithms cannot achieve a ratio better than 4. For trees, the problem remains NP-hard to solve exactly, and there is a polynomial-time 2-approximation, along with a tight barrier result showing that the class of $\ell$-straying algorithms cannot achieve a ratio better than 2. Weighted token swapping with $\{0,1\}$ weights is much harder to approximation: it is NP-hard to approximate even to a factor of $(1-\varepsilon) \cdot \ln n$ for any constant $\varepsilon>0$. Restricting to positive weights, no approximation algorithms are known, and the only known lower bounds are those inherited directly from the unweighted version. We provide the first approximation algorithms for weighted token swapping on both trees and general graphs, along with tight barrier results. Letting $w$ and $W$ be the minimum and maximum token weights, our approximation ratio is $2+2W/w$ for general graphs and $1+W/w$ for trees.