Approximation Algorithms for α-bisub modular Function Maximization Subject to Matroid Constraint

We design an approximation algorithm for maximizing α-bisubmodular function with matroid constraint,where the α-bisubmodular function is a generalization of a bisubmodular function. The concept of α-bisubmodularity is provided by Huber, Krokhin, and Powell [[1], 2014], rank function of delta-matroids andthe cut capacity of directed networks have α-bisubmodularity. We consider the two cases of the problem,monotone and non-monotone objective function, respectively.We also show that the running time ispolynomial.