A Survey on Covering Supermodular Functions
A Survey on Covering Supermodular Functions
复制标题
覆盖超模函数的综述
DOI：
10.1007/978-3-540-76796-1_6
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Tamás Király
中科院分区：
文献类型：
--
作者：
A. Frank;Tamás Király
在本次调查中，我们介绍了一些问题的最新进展，这些问题可以描述为图或超图的构造，这些图或超图涵盖了具有超模或相关属性的某些集合函数。其中包括广泛的网络设计和连通性增强和定向问题，以及着色和匹配的一些结果。在本文的第一部分中，我们调查了由超模类型集合函数定义的各种系统的全对偶积分（TDI）属性得出的结果。该调查的目的之一是强调放宽超模性属性以包含更广泛的集合函数的重要性。我们展示了这些松弛如何导致对不同类型应用的统一理解。第二部分致力于根据我们目前的知识，无法使用全对偶完整性来解释的结果。我们想证明，在过去 15 年里，围绕各种连通性增强问题，已经发展出一种独立于总对偶完整性的广泛理论。我们的调查集中在理论基础上，并不包括应用程序的每个细节，因为这些应用程序中的大多数都在第一作者的另一篇调查论文中进行了详细描述（Frank 2006）。 Schrijver (2003) 的综合著作《组合优化：多面体和效率》也是与子模函数相关的丰富成果资源。应该指出的是，子模性和超模性在本文未讨论的领域有多种应用。特别值得一提的是 Fujishige (2005) 的《Submodular Functions and Optimization》一书和 Murota (2003) 的《Discrete Convex Analysis》一书。前者解释了子模函数理论的基础并描述了子模分析的方法，而后者通过使用连续优化的思想扩展子模函数理论，提出了非线性离散优化的统一框架。我们的调查重点关注这些书中未详细讨论的主题。
In this survey we present recent advances on problems that can be described as the construction of graphs or hypergraphs that cover certain set functions with supermodular or related properties. These include a wide range of network design and connectivity augmentation and orientation problems, as well as some results on colourings and matchings.In the first part of the paper we survey results that follow from the totally dual integral (TDI) property of various systems defined by supermodular-type set functions. One of the aims of the survey is to emphasize the importance of relaxing the supermodularity property to include a wider range of set functions. We show how these relaxations lead to a unified understanding of different types of applications.The second part is devoted to results that, according to our current knowledge, cannot be explained using total dual integrality. We would like to demonstrate that an extensive theory independent of total dual integrality has been developed in the last 15 years, centered around various connectivity augmentation problems.Our survey concentrates on the theoretical foundations, and does not include every detail on applications, since the majority of these applications are described in detail in another survey paper by the first author (Frank 2006). The comprehensive book “Combinatorial Optimization: Polyhedra and Efficiency” by Schrijver (2003) is also a rich resource of results related to submodular functions.It should be noted that sub- and supermodularity have several applications in areas not discussed in this paper. In particular, we should mention the book “Submodular Functions and Optimization” by Fujishige (2005) and the book “Discrete Convex Analysis” by Murota (2003). The former explains the foundations of the theory of submodular functions and describes the methods of submodular analysis, while the latter presents a unified framework for nonlinear discrete optimization by extending submodular function theory using ideas from continuous optimization. Our survey focuses on topics not discussed in detail in those books.