On the Shadow Simplex Method for Curved Polyhedra
On the Shadow Simplex Method for Curved Polyhedra
复制标题
弯曲多面体的阴影单纯形法
DOI：
10.1007/s00454-016-9793-3
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
Nicolai Hähnle
中科院分区：
文献类型：
--
作者：
D. Dadush;Nicolai Hähnle
我们研究了满足某些“离散曲率”下界的多面体单纯形法，该下界强制边界始终以锐角与顶点相交。受具有完全单模约束矩阵的线性规划的推动，Bonifas 等人的最新结果。 （Discrete Comput. Geom. 52(1):102–115, 2014）、Brunsch 和 Röglin（自动机、语言和编程。第一部分，第 279–290 页，Springer, Heidelberg, 2013）以及 Eisenbrand 和 Vempala (http://arxiv.org/abs/1404.1568, 2014) 有所改进我们对这种多面体的理解。我们开发了一种新型的阴影单纯形方法的对偶分析，它为改进所有前面提到的结果提供了一个干净而强大的工具。我们的方法受到 Bonifas 和第一作者最近工作的启发（Indyk P (ed) Proceedings of the Twenty-Sixth Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 295–314, SIAM, 2015），他分析了一个非常相似的过程，作为预处理最近向量问题算法的一部分。对于我们的第一个结果，我们获得 O(n2δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} 的构造直径界限\begin{document}$$O(\frac{n^2}{\delta } \ln \frac{n}{\delta })$$\end{document} 对于 n 维多面体，曲率参数 δε(0,1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta \in (0,1]$$\end{document}。对于完全单模约束矩阵产生的多面体类，这意味着 O(n3lnn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} 的界限\usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^3 \ln n)$$\end{document} 对于线性优化，给定初始可行顶点，我们证明可以使用预期找到最佳顶点。 O(n3δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{n^3}{\delta } \ln \frac{n}{\delta })$$\end{document} 单纯形主元，每个主元需要 O(mn) 时间来计算，其中 m 是约束数，可以使用 O(mn3δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} 找到初始可行解。 \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{m n^3}{\delta } \ln \frac{n}{\delta })$$\end{document} 枢轴步骤。
We study the simplex method over polyhedra satisfying certain “discrete curvature” lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent results of Bonifas et al. (Discrete Comput. Geom. 52(1):102–115, 2014), Brunsch and Röglin (Automata, languages, and programming. Part I, pp. 279–290, Springer, Heidelberg, 2013), and Eisenbrand and Vempala (http://arxiv.org/abs/1404.1568, 2014) have improved our understanding of such polyhedra. We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author (in: Indyk P (ed) Proceedings of the Twenty-Sixth Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 295–314, SIAM, 2015), who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing. For our first result, we obtain a constructive diameter bound of O(n2δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{n^2}{\delta } \ln \frac{n}{\delta })$$\end{document} for n-dimensional polyhedra with curvature parameter δ∈(0,1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta \in (0,1]$$\end{document}. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of O(n3lnn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^3 \ln n)$$\end{document}. For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected O(n3δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{n^3}{\delta } \ln \frac{n}{\delta })$$\end{document} simplex pivots, each requiring O(mn) time to compute, where m is the number of constraints. An initial feasible solution can be found using O(mn3δlnnδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{m n^3}{\delta } \ln \frac{n}{\delta })$$\end{document} pivot steps.
赫希猜想适用于正常旗形复合体
DOI：
10.1287/moor.2014.0661
发表时间：
2014
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Karim Adiprasito;Bruno Benedetti
通讯作者：
Bruno Benedetti