权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Randomized approaches to combinatorial packing and covering problems

组合包装和覆盖问题的随机方法

基本信息

批准号：
EP/M009408/1
负责人：
Daniela Kuehn
金额：
$ 32.91万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM009408%2F1
关键词：
Randomized approaches combinatorial packing covering

项目摘要

Many important questions can be formulated as covering and packing problems. This makes the study of such problems crucial both from an algorithmic and a more structural point of view. Recent ideas and methods from discrete probability theory have led to several breakthroughs in the area, with the potential to reshape the field. Here in a packing problem the task is to organize as many elements of a given structure as possible into suitable disjoint substructures. In a covering problem the task is to cover all elements of a given structure by as few as possible suitable substructures (which are not necessarily disjoint). These problems can be viewed as "duals" of each other. In particular, their solutions sometimes coincide, in which case we obtain a decomposition of the given structure.A classical example occurs in design theory: under suitable divisibility conditions a Steiner Triple System gives a decomposition of the edges of a complete graph into edge-disjoint triangles, i.e. the optimal solution of the triangle packing problem equals that of the triangle covering problem. Such problems have a long history going back to the 19th century and have many applications, e.g. to testing, statistical design and coding theory. The project intends to approach long-standing questions concerning optimal packings in non-complete host graphs. These have applications e.g. in communication networks. Another related strand is to study packings and coverings involving more complex structures such as spanning trees and resolvable designs. We intend to provide a powerful algorithmic tool for such questions which can be viewed as near-optimal packing version of the famous Blow-up Lemma. This would have numerous structural and algorithmic applications. Furthermore, the packing and covering viewpoint can be valuable in a much broader context. In particular, we propose to employ it to study the Boolean Satisfiability Problem k-SAT. The k-SAT problem is computationally intractable and of fundamental importance in theoretical computer science. Again, the probabilistic perspective has proved to be invaluable. By formulating the k-SAT problem as a hypergraph covering problem, we will aim to solve key open problems regarding statistical properties of random k-SAT formulas.

许多重要的问题都可以表示为覆盖问题和装箱问题。这使得对这类问题的研究无论是从算法角度还是从更具结构性的角度来看都至关重要。最近来自离散概率理论的想法和方法导致了该领域的几项突破，有可能重塑该领域。在这里，在布局问题中，任务是将给定结构中尽可能多的元素组织到合适的不相交的子结构中。在覆盖问题中，任务是用尽可能少的合适的子结构(不一定是不相交的)来覆盖给定结构的所有元素。这些问题可以被看作是彼此的“二重奏”。具体地说，它们的解有时是重合的，在这种情况下，我们得到了给定结构的分解。设计理论中出现了一个经典的例子：在适当的可分性条件下，Steiner三元系将完全图的边分解成边不相交的三角形，即三角形布局问题的最优解等于三角形覆盖问题的最优解。这类问题有很长的历史，可以追溯到19世纪，并有许多应用，例如测试、统计设计和编码理论。该项目旨在解决长期存在的关于非完全宿主图中的最优填充的问题。这些具有例如在通信网络中的应用。另一个相关的方向是研究涉及更复杂结构的填充和覆盖，如生成树和可分解设计。我们打算为这类问题提供一个强大的算法工具，它可以被视为著名的Blow-up引理的近最优包装版本。这将会有许多结构和算法上的应用。此外，包装和覆盖的观点在更广泛的背景下可能是有价值的。特别地，我们建议将其应用于研究布尔可满足性问题k-SAT。K-SAT问题在计算上是一个棘手的问题，在理论计算机科学中具有重要意义。事实再次证明，概率观点是无价的。通过将k-SAT问题描述为超图覆盖问题，我们将致力于解决关于随机k-SAT公式的统计性质的关键公开问题。