preprint · arXiv (Cornell University) · 2023

A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint

Cited by 0Open access

Abstract

A $k$-submodular function is a generalization of the submodular set function. Many practical applications can be modeled as maximizing a $k$-submodular function, such as multi-cooperative games, sensor placement with $k$ type sensors, influence maximization with $k$ topics, and feature selection with $k$ partitions. In this paper, we provide a unified continuous greedy algorithm for $k$-submodular maximization problem under a down-monotone constraint. Our technique involves relaxing the discrete variables in a continuous space by using the multilinear extension of $k$-submodular function to find a fractional solution, and then rounding it to obtain the feasible solution. Our proposed algorithm runs in polynomial time and can be applied to both the non-monotone and monotone cases. When the objective function is non-monotone, our algorithm achieves an approximation ratio of $(1/e-o(1))$; for a monotone $k$-submodular objective function, it achieves an approximation ratio of $(1-1/e-o(1))$.

Cite this paper

APA 7

Zhang, H., & Luo, W. (2023). A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2311.18239

MLA 9

Zhang, Hongyang, and Wenchang Luo. “A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint.” arXiv (Cornell University), 2023, https://doi.org/10.48550/arxiv.2311.18239.

Chicago

Zhang, Hongyang, and Wenchang Luo. 2023. “A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2311.18239.

Harvard

Zhang, H. and Luo, W. (2023) ‘A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2311.18239.

BibTeX

@misc{zhang2023unified,
  title = {{A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint}},
  author = {Zhang, Hongyang and Luo, Wenchang},
  journal = {arXiv (Cornell University)},
  year = {2023},
  doi = {10.48550/arxiv.2311.18239}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.