跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1959新增论文
+1550其中 AI 相关
+212已有论文修订
+84新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

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

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 23:19(北京时间)
版本更新 · v2arXiv:2611.12680

Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method

Yann Disser, Nils Mosis

原文摘要

Wolfe's method computes the point of minimum Euclidean norm in the convex hull of finitely many points. The method is parameterized by an insertion rule and it has been an open problem whether Wolfe's original rule guarantees a polynomial number of iterations (De Loera, Haddock, and Rademacher; STOC'18). We resolve this question by proving an exponential lower bound. In fact, we establish a tight connection to the simplex method for linear programming that allows us to transfer many lower bounds for simplex pivot rules to corresponding insertion rules of Wolfe's method. These include not only Wolfe's linopt rule via Dantzig's pivot rule, but also many other classical, randomized and history-based rules. As a corollary, we obtain the first exponential example for the Lawson-Hanson algorithm for nonnegative least squares, as well as PSPACE-hardness of deciding whether the linopt rule ever uses a given point.

math.OC · cs.DS

版本更新 · v3arXiv:2507.16648

An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming

Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis

原文摘要

We prove that, for every fixed $ε\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\vec c^{\top}\vec x$ subject to linear constraints, regardless of the pivot rule used. Our lower bound therefore holds for objectives arbitrarily close to the linear case $ε=0$, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. The special case $ε=1$ yields a lower bound in convex quadratic maximization. This improves on the best previously known lower bound [IPCO 2025] requiring polynomial objectives of degree $ω(\log d)$ in dimension $d$ and firmly resolves the open question of whether a constant degree suffices. Our result is based on a novel extended formulation, recursively constructed using deformed products. Its key feature is that it projects onto a polygonal approximation of a parabola while preserving all of its exponentially many vertices. We define a convex objective with a single non-linear variable that forces the active-set method to follow the parabolic boundary of this projection, without allowing any shortcuts along chords corresponding to edges of its full-dimensional preimage.

cs.DM · cs.CC · cs.DS · math.CO