跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1199新增论文
+950其中 AI 相关
+132已有论文修订
+97新增 AI 导读

arXiv 最近完成扫描:2026-11-20 08:48 · 全站最近入库:2026-11-20 16:53各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-20 08:48最近发现新增版本:2026-11-20 16:53库内论文最新更新时间:2026-11-20 02:59

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

28,609 已收录论文23,738 AI 相关8,785 有修订112 HF 社区发现

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 08:46(北京时间)
版本更新 · v3arXiv:2607.18935

Online Stochastic Matchings: Stability on Hypergraphs

Fabien Mathieu

原文摘要

In stochastic dynamic matching, items of several classes arrive at rates $λ$ and leave in compatible groups. When groups may exceed two items, as in quantum switches or organ exchange, compatibility is described by the incidence matrix $A$ of a hypergraph, whose entries count how many items of each class a group consumes (single-class hyperedges can model discards). We call a system stabilizable if some matching policy keeps large queues rare in the long run, and show that this holds if and only if the conservation equation $Aμ= λ$ admits a nonnegative solution whose support induces a surjective submatrix. Equivalently, $λ$ lies in the interior of the cone generated by the hyperedges. The condition is necessary for all policies, including idling and clairvoyant ones. It is sufficient through one explicit policy: the rewardless counterpart of the Extended Greedy Primal--Dual policy of Nazari and Stolyar (2019) stabilizes every stabilizable system without knowledge of the rates, and its mean queue length is explicitly bounded. Approaching a solution whose support is not surjective has a cost, under every policy: matching rates within $ε$ of it force mean queues of order at least $1/ε$. On simple graphs, some greedy policies stabilize every stabilizable system. On a small hypergraph with a single hyperedge of size three, every greedy policy is unstable on an open set of stabilizable rates. This shows that no greedy policy, nor any family of greedy policies, can approach maximal stability on hypergraphs: idling is necessary. We also settle two cases explicitly: the complete $k$-uniform hypergraph (the $k$-partite quantum switch), which is stabilizable exactly when no link generates a fraction $1/k$ or more of the total rate, and the Fano plane.

cs.NI

新论文 · v1arXiv:2611.17989

The Exact Stabilization Time of Self-Stabilizing Coloring: Mean, Variance, and Distribution

{É}lie de Panafieu, Fabien Mathieu, Maria Gradinariu Potop-Butucaru, S{é}bastien Tixeuil

原文摘要

The worst-case stabilization time of a self-stabilizing algorithm usually says little about its typical behavior beyond the order of magnitude. This paper revisits the classical self-stabilizing $Delta+1$ coloring algorithm with vertices activated at random, one at a time (the random central daemon). Considering the number of color changes as a random variable, we study its mean, variance and, on several families of graphs, its exact distribution. The analysis rests on a reduction: a vertex changes color, at most once, exactly when it is not a local maximum of a uniformly random labeling of the vertices, maxima being taken among the neighbors that share its initial color (the monochrome initial configuration is the slowest case). What can be predicted depends on what is known of the graph. The degree distribution (the view at distance one) gives the mean. The variance needs the view at distance two, in particular the triangles, and the full law needs the whole graph. We give closed-form results, from monochrome and from uniformly random initial configurations, on paths, cycles, random trees, Erdős-R{é}nyi graphs and bipartite random graphs. From a monochrome start, the mean stays within a factor two of the worst case, whereas the variance ranges from zero (disjoint cliques) to order $n^2$ (the star on $n$ vertices)..

cs.DC · math.CO · math.PR