跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

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

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.20795

Speed-Robust Scheduling for Total Completion Time

Moritz Buchem, Nicole Megow, Morten Weber

原文摘要

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into $M$ bags before an adversary reveals the speeds of at most $M$ machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~$13/12$, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between $31/30\approx1.0333$ and $28/27\approx1.0370$, well below the optimal makespan factor of about $1.2071$. General speeds make the problem strictly harder: no deterministic algorithm is better than $1.2669$-robust, already for infinitesimally small jobs. We give a $25/16$-robust algorithm for arbitrary processing times and improve the guarantee to $1681/1152\approx1.4592$ for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

cs.DS · cs.DM

新论文 · v1arXiv:2611.12034

The Power of Migration on Identical Machines is Two

Nicole Megow, Bart Zondervan

原文摘要

We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on $m$ machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that $6m-5$ machines suffice and gave a polynomial-time construction using $12m-5$ machines, whereas $2m-1$ machines may be necessary. We close this gap, which has been open for more than 25 years: $2m-1$ machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on $m$ machines is $(2m-1)$-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe exchanges to compute a coloring in polynomial time. Second, we construct a supercanonical schedule with polynomially many processing blocks by shrinking job windows as far as possible while preserving feasibility and solving a min-cost flow problem.

cs.DS · cs.DM

新论文 · v1arXiv:2611.04559

Distributionally Robust Search: The Power of Information and the Limits of Moments

Nicole Megow, Cliff Stein, Jose Verschae

原文摘要

We study binary search for a target drawn from a distribution on $n$ ordered elements. The cost is the expected number of comparison queries. In our distributionally robust framework, the algorithm knows only an uncertainty set containing the distribution and minimizes its worst-case approximation ratio against an optimal strategy that knows the distribution. Collections of uncertainty sets capture different forms of information: quantiles, moments, general linear measurements, or approximate CDFs. This framework quantifies how much and what form of information is needed for near-optimal search. Our main result separates moments from general linear measurements. Although $n-1$ moments determine the distribution exactly, for every constant $δ\in(0,1)$, the first $n^{1-δ}$ exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains $Ω(\log n)$. In contrast, for every constant $\varepsilon\in(0,1)$, $O(n^\varepsilon\log^4 n)$ suitably chosen linear measurements suffice for an $O(1/\varepsilon)$-approximation. The limitation lies in the measurements chosen, rather than linearity itself. Using LP duality and polynomial bounds of Rakhmanov and Bernstein, we construct distributions with identical moments and mass concentrated at different positions. For the upper bound, we combine dyadic sketches and Johnson--Lindenstrauss embeddings with a truncated median-search algorithm that converts uniform CDF approximation into search guarantees. Measuring information in bits, we prove a lower bound of $Ω(1/\varepsilon)$ on the approximation ratio for summaries of any form using at most $\frac12 n^\varepsilon\log n$ bits, for every sufficiently small constant $\varepsilon>0$. Quantiles match this within constant factors. For Kolmogorov balls of radius $n^{-\varepsilon}$ the optimal approximation ratio is $Θ(1/\varepsilon)$.

cs.DS · cs.DM