Approximation Algorithms for \(\alpha\)-bisubmodular Function Maximization Subject to Matroid Constraint
Wenqi Wang *
School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, China.
*Author to whom correspondence should be addressed.
Abstract
We design an approximation algorithm for maximizing \(\alpha\)-bisubmodular function with matroid constraint, where the \(\alpha\)-bisubmodular function is a generalization of a bisubmodular function. The concept of \(\alpha\)- bisubmodularity is provided by Huber, Krokhin, and Powell [[1], 2014], rank function of delta-matroids and the cut capacity of directed networks have \(\alpha\)-bisubmodularity. We consider the two cases of the problem, monotone and non-monotone objective function, respectively. We also show that the running time is
polynomial.
Keywords: \(\alpha\)-bisubmodular function, combinatorial optimization, greedy algorithm, matroid constraint