English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A natural and important generalization of submodularity -- $k$-submodularity-- applies to set functions with $k$ arguments and appears in a broad range ofapplications, such as infrastructure design, machine learning, and healthcare.In this paper, we study maximization problems with $k$-submodular objectivefunctions. We propose valid linear inequalities, namely the $k$-submodularinequalities, for the hypograph of any $k$-submodular function. This class ofinequalities serves as a novel generalization of the well-known submodularinequalities. We show that maximizing a $k$-submodular function is equivalentto solving a mixed-integer linear program with exponentially many$k$-submodular inequalities. Using this representation in a delayed constraintgeneration framework, we design the first exact algorithm, that is not acomplete enumeration method, to solve general $k$-submodular maximizationproblems. Our computational experiments on the multi-type sensor placementproblems demonstrate the efficiency of our algorithm in constrained nonlinear$k$-submodular maximization problems for which no alternative compactmixed-integer linear formulations are available. The computational experimentsshow that our algorithm significantly outperforms the only available exactsolution method -- exhaustive search. Problems that would require over 13 yearsto solve by exhaustive search can be solved within ten minutes using ourmethod.

An Exact Cutting Plane Method for $k$-submodular Function Maximization