A Survey on Covering Supermodular Functions

András Frank () and Tamás Király ()
Additional contact information
András Frank: Eötvös Loránd University, Department of Operations Research
Tamás Király: Eötvös Loránd University, Department of Operations Research

Chapter 6 in Research Trends in Combinatorial Optimization, 2009, pp 87-126 from Springer

Abstract: Summary 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.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_6

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().