Generalized minimum 0-extension problem and discrete convexity

arXiv2109.10203MaRDI QIDQ6504682FDOQ6504682

Authors: Martin Dvořák, Vladimir Kolmogorov 

Abstract: Given a fixed finite metric space $(V,mu)$, the {em minimum $0$-extension problem}, denoted as $t0mbox-Ext[mu]$, is equivalent to the following optimization problem: minimize function of the form $minlimit{s}_{xin{V}^n}su{m}_i{f}_i(x_i)+su{m}_{ij}{c}_{ij}mu(x_i,x_j)$ where $c_{ij},c_{vi}$ are given nonnegative costs and $f_i:VightarrowmathbbR$ are functions given by $f_i(x_i)=su{m}_{vinV}{c}_{vi}mu(x_i,v)$. The computational complexity of $t0mbox-Ext[mu]$ has been recently established by Karzanov and by Hirai: if metric $mu$ is {em orientable modular} then $t0mbox-Ext[mu]$ can be solved in polynomial time, otherwise $t0mbox-Ext[mu]$ 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^{a}tural$-convex functions. We consider a more general version of the problem in which unary functions $f_i(x_i)$ can additionally have terms of the form $c_{uv;i}mu(x_i,u,v)$ for $u,vinF$, where set $$ is fixed. We extend the complexity classification above by providing an explicit condition on $(mu,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 $t0mbox-Ext[mu]$ on orientable modular graphs.

This page was built for publication: Generalized minimum 0-extension problem and discrete convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504682)