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

In this paper, we study classes of discrete convex functions: submodularfunctions on modular semilattices and L-convex functions on oriented modulargraphs. They were introduced by the author in complexity classification ofminimum 0-extension problems. We clarify the relationship to other discreteconvex functions, such as $k$-submodular functions, skew-bisubmodularfunctions, L$^\natural$-convex functions, tree submodular functions, andUJ-convex functions. We show that they are actually viewed assubmodular/L-convex functions in our sense. We also prove a sharp iterationbound of the steepest descent algorithm for minimizing our L-convex functions.The underlying structures, modular semilattices and oriented modular graphs,have rich connections to projective and polar spaces, Euclidean building, andmetric spaces of global nonpositive curvature (CAT(0) spaces). By utilizingthese connections, we formulate an analogue of the Lov\'asz extension,introduce well-behaved subclasses of submodular/L-convex functions, and showthat these classes can be characterized by the convexity of the Lov\'aszextension. We demonstrate applications of our theory to combinatorialoptimization problems that include multicommodity flow, multiway cut, andrelated labeling problems: these problems have been outside the scope ofdiscrete convex analysis so far.

L-convexity on graph structures