Majorisation-minimisation algorithms for minimising the difference\n between lattice submodular functions

2019/05/31 by Conor McMeel, McMeel, Conor, Panos Parpas +1
Computer Science · Materials Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Copper Interconnects and Reliability

paper · pdf · doi:10.48550/arxiv.1905.13492

Abstract

We consider the problem of minimising functions represented as a difference\nof lattice submodular functions. We propose analogues to the SupSub, SubSup and\nModMod routines for lattice submodular functions. We show that our\nmajorisation-minimisation algorithms produce iterates that monotonically\ndecrease, and that we converge to a local minimum. We also extend additive\nhardness results, and show that a broad range of functions can be expressed as\nthe difference of submodular functions.\n

Related

• Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
• On Unconstrained Quasi-Submodular Function Optimization
• Towards Minimizing k-Submodular Functions
• A Reduction for Optimizing Lattice Submodular Functions with Diminishing\n Returns
• Discrete and Continuous Difference of Submodular Minimization