跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1865新增论文
+1473其中 AI 相关
+176已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-17 04:58 · 全站最近入库:2026-11-17 17:12各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 17:26 — 2026-11-17 17:26(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 17:12库内论文最新更新时间:2026-11-17 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,692 已收录论文21,414 AI 相关7,613 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
新论文 · v1arXiv:2611.13600

Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection

Michael Emmerich, Soumen Atta

原文摘要

We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but NP-hard in the plane. Adapting the proxy lemma of Ceccarello et al. gives an efficient parameterized approximation scheme (EPAS) for fixed Euclidean dimension and fixed $s>0$. To sharpen the bound, we start with a geometric packing. Farthest-first traversal gives $2k$ centers separated by at least the last insertion distance $r$. If one site of an optimum is removed, each of the $k-1$ remaining sites excludes at most one center closer than $r/2$, leaving at least $k+1$ centers free. The new step is a discrete exchange bound: the removed site's interaction energy is at most the average it would contribute at those free centers. In the plane at $s=2$, this reduces the representative bound from $O(k^2\log(2k)/\varepsilon^2)$ for a packing estimate of total energy to $O(k\log(2k)/\varepsilon^2)$, independently of $n$. Rational planar examples show that the resulting separation scale $r/\sqrt{\log(2k)}$ is sharp. A $(1+\varepsilon)$ approximation on rational planar sites takes $O(nk+n\log n)+(C\log(2k)/\varepsilon^2)^k$ operations of polynomial bit cost. The observed number $M$ of representatives determines the search size $\binom{M}{k}$. With one million sites, $k=5$ and $\varepsilon=1/2$, the exchange grid left 252 subsets on clustered inputs and about $9.3\times10^{26}$ on uniform inputs. The method extends to metrics of bounded doubling dimension and to compact domains with effective geometric routines, including filled simple polygons. At $s=2$, exact decision on metrics with nonzero distances in $\{1,2\}$ is W[1]-complete in $k$. A gap that shrinks with $k$ rules out a deterministic EPAS on unrestricted metrics unless FPT = W[1].

cs.CG · cs.CC · cs.DS