Submodular Percolation: A Proposal for Research in Combinatorics

子模渗滤：组合学研究的提案

• 批准号: 0600876
• 负责人: Peter Winkler
• 金额: --
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600876&HistoricalAwards=false
• 关键词: Submodular; Percolation; Proposal; Research; Combinatorics

The proposer seeks to explore a combinatorial thread which involves algorithms, optimization and statistical physics; and in particular, connects process scheduling, submodular systems, and a form of percolation. The problem of scheduling two real sequences so as to minimize their maximum pairwise sum leads to a preorder on sequences, called the ``worm order.'' Remarkably, for any submodular function on a finite distributive lattice, there is a maximal chain whose function values are minimum in the worm order relative to all paths from 0 to 1 in the lattice. One consequence is explicit representation of the theta function for a form of coordinate percolation, in which random reals are assigned to axis points on the plane grid, and grid points inherit the sum of the two reals assigned to their coordinates. Points whose value exceeds some bound are deleted, and the theta function measures the probability that one can walk to infinity on what remains of the grid.The proposed line of research aims to better understand percolation, originally a model for physical processes such as water seeping through a porous material. However, a variety of additional applications arise when a complex process must be scheduled, and the issue is whether backward steps are needed. For example, if the components of a computer system must be upgraded, is it possible that a temporary downgrade will be needed at some point to keep things running smoothly? If a line of searchers are sweeping a forest in search of a lost child, can they do so without covering any area more than once? The proposed work will identify conditions under which one can guarantee that, if the process can be accomplished at all, then it can be done without retreating.

建议者试图探索涉及算法，优化和统计物理学的组合线程；特别是，连接过程调度，子模块系统和渗透形式。 安排两个真实序列以最大程度地减少其最大成对总和的问题导致序列的预订，称为``蠕虫顺序''。值得注意的是，对于有限分布晶格上的任何下二个函数，有一个最大链中，其功能值相对于蠕虫的最小值，相对于所有路径在所有路径上是最小的，从0到1中的蠕虫序列。 结果之一是将theta函数的明确表示为坐标渗透的形式，其中随机实数被分配给平面网格上的轴点，网格点继承了分配给其坐标的两个真实物的总和。 删除了价值超过某些绑定的点，而Theta功能可以测量人们可以在网格上剩下的剩余的概率。拟议的研究线旨在更好地理解渗透，最初是一种物理过程的模型，例如通过多孔材料渗入水。 但是，当必须安排复杂的过程时，会出现各种其他应用程序，问题是是否需要向后步骤。例如，如果必须升级计算机系统的组件，是否需要在某个时候需要临时降级才能使情况顺利进行？ 如果一系列搜索者正在扫荡森林寻找失去的孩子，他们可以在不覆盖任何区域的情况下这样做吗？ 拟议的工作将确定可以保证的条件，如果该过程完全可以完成，那么它可以在不撤退的情况下完成。