Submodularity of a Set Label Disagreement Function
This work provides a theoretical property for optimization methods in hypergraph applications, but it is incremental as it focuses on analyzing an existing function type.
The paper investigates the submodularity of a set label disagreement function, which measures deviation from the dominant label in binary variables, and finds that it can be used as a cost function in combinatorial optimization for hypergraph problems.
A set label disagreement function is defined over the number of variables that deviates from the dominant label. The dominant label is the value assumed by the largest number of variables within a set of binary variables. The submodularity of a certain family of set label disagreement function is discussed in this manuscript. Such disagreement function could be utilized as a cost function in combinatorial optimization approaches for problems defined over hypergraphs.