Jun, 2022

树的最大线性排列问题（基于 projectivity 和 planarity）

PDF
TL;DR本文研究了最大线性排列问题（MaxLA）的两个变体，即基于免费树和基于根树的平面和投影变体。针对树的平面和投影 MaxLA 问题，提出了相应的线性时间和空间的算法，并证明了最大投影和平面排列的几个性质，同时表明毛毛虫树是平面 MaxLA 问题中所有尺寸固定的树中最优的，从而推广了前人在树上的极值结果。
linear arrangementgraphmaxlaplanar variantprojective variant
发现论文，激发创造
  • 树的平面线性化中边长度期望和的线性时间计算

    本篇文章研究依赖图的句法结构，针对平面的排列方法和投射的排列方法，分别提出了预期边长总和的计算方法，并用一个包含词语的句子来给出了平面排列的数量或生成平面随机排列的有效算法。

    Jul, 2022

  • 图形化房屋分配

    本研究在经典的分配问题基础上，研究了基于社交网络的分配问题，目标是通过最小化代理人之间的嫉妒程度来实现公平分配；同时，该研究还贡献了基于图结构的问题结构与计算结果，提出了一个名为 “可分离性” 的概念，可以在某些图结构中实现高效的最优分配算法。

    Jan, 2023

  • 随机线性排列的边长度之和

    该研究探讨了在随机线性排列的节点中边长之和的分布情况，可用于各个领域；得到了任意图形和树的 1 阶、2 阶、方差的紧凑公式；并分析了该方差在 Erdos-Renyi 图中的演化和在均匀随机树中的缩放。

    May, 2019

  • 分区平面图算法

    计算复杂性、选区分割、地图重新划分问题、平面图和逼近算法。

    Dec, 2023

  • 平面计数问题的复杂性

    在平面图情况下，我们证明了与各种满足性、图形和组合问题相关的计数问题的 #P 难度。另外，当局限于计划实例时，我们证明了具有不明确解决方案性的满足性问题的 NP 完全性和与唯一满足性问题相关的随机多项式可简化的 DP 完全性。假设 P≠NP，则以上结果的一个推论是：不存在 ε- 逼近算法，用于在整数上计划线性不等式约束系统的最大化或最小化线性目标函数问题。

    Sep, 1998

  • 树的随机投影线性化中边长期望和的线性时间计算

    本文提供一种新的算法来计算句子的依存距离期望值，在统计上足够准确，时间复杂度为 $n$。此外，文章还发现了星形树（star tree）在该算法中具有最大化作用，提出了一种可以找到最小化依存距离期望值的树的算法。

    Jul, 2021

  • 样本压缩的几何方法

    本文通过对有限最大概念类的压缩的几何系统性研究，证明了 Piecewise-Linear 超平面排列能够通过等高线法压缩任意有限最大类，从而证明了 Kuzmin 和 Warmuth 的猜想，并说明了一些 d - 最大化类无法嵌入到 VC 维度为 d+k 的任何最大类中。

    Nov, 2009

  • 狭窄空间内的惰性整理规划

    该论文提出了一种懒惰计算法并结合局部单调求解器与全局规划器，以高效地解决在密闭空间中进行的物体重新排列问题。该算法可在考虑物体间可达性约束的情况下，快速发现物体间依赖关系，并在求解目标时拓展局部最优解来移动物体以完成整个任务，成功应用于高达 16 个物体的场景中，并且解决速度和解决质量都优于目前现有算法。

    Mar, 2022

  • 小树幅线性规划的近线性时间算法：健壮中心路径的多尺度表示

    本文提出了一种基于内点法和树分解的线性规划问题求解算法，可以在近似相对误差为 ε 的情况下，在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题，其中 tw 是输入图的树宽，并且是第一个时间复杂度与子问题 Ax=b 的最快时间复杂度相匹配的算法。

    Nov, 2020

  • 自然参数空间中线性规划相位最大值法的凸相位恢复初等证明

    该研究论文探讨相位恢复问题，通过探讨一种针对随机测量下线性编程的凸形式 PhaseMax 算法的校验方法，简化了 Wirtinger Flow-like 方法的技术论证和之前基于统计学习理论和几何概率论的证明，并证明了在最优样本复杂度下，PhaseMax 准确地从随机测量中回收实值向量。

    Nov, 2016