Skip to content
Research Article Open access CC BY 4.0

Approximation Algorithms for \(\alpha\)-bisubmodular Function Maximization Subject to Matroid Constraint

Wenqi Wang

Journal of Advances in Mathematics and Computer Science · pp. 42–48 · Published 21 Feb 2023

10.9734/jamcs/2023/v38i31750

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.

\(\alpha\)-bisubmodular function combinatorial optimization greedy algorithm matroid constraint

References (13)

  1. 1 Advances in neural information processing systems 7 [DOI]
  2. 2 An analysis of approximations for maximizing submodular set functions—I [DOI]
  3. 3 Maximizing a Monotone Submodular Function Subject to a Matroid Constraint [DOI]
  4. 4 A note on maximizing a submodular set function subject to a knapsack constraint [DOI]
  5. 5 Best Algorithms for Approximating the Maximum of a Submodular Set Function [DOI]
  6. 6 Fast algorithms for maximizing submodular functions [DOI]
  7. 7 Monotone k -submodular function maximization with size constraints
  8. 8 Polynomial combinatorial algorithms for skew-bisubmodular function minimization [DOI]
  9. 9 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms [DOI]
  10. 10 On maximizing a monotone k-submodular function subject to a matroid constraint [DOI]
  11. 11 Improved randomized algorithm for $k$-submodular function maximization [DOI]
  12. 12 On maximizing a monotone $k$-submodular function under a knapsack constraint [DOI]
  13. 13 Improved Approximation Algorithms for k-Submodular Function Maximization [DOI]

Cited by 0

No indexed citations yet.

Related research

Article metrics

Real usage data collected on this platform.

18

Page views

0

PDF downloads

3

Outbound clicks

0

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.