--- res: bibo_abstract: - "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Martin foaf_name: Dvorak, Martin foaf_surname: Dvorak foaf_workInfoHomepage: http://www.librecat.org/personId=40ED02A8-C8B4-11E9-A9C0-453BE6697425 orcid: 0000-0001-5293-214X - foaf_Person: foaf_givenName: Vladimir foaf_name: Kolmogorov, Vladimir foaf_surname: Kolmogorov foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87 bibo_doi: 10.1007/s10107-024-02064-5 dct_date: 2024^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0025-5610 - http://id.crossref.org/issn/1436-4646 dct_language: eng dct_publisher: Springer Nature@ dct_subject: - minimum 0-extension problem - metric labeling problem - discrete metric spaces - metric extensions - computational complexity - valued constraint satisfaction problems - discrete convex analysis - L-convex functions dct_title: Generalized minimum 0-extension problem and discrete convexity@ ...