Generalized minimum 0-extension problem and discrete convexity

Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv, 2109.10203.

Download
OA Generalized-0-Ext.pdf 603.67 KB
Preprint | Unpublished | English
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.
Publishing Year
Date Published
2021-09-21
Journal Title
arXiv
Article Number
2109.10203
IST-REx-ID

Cite this

Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv.
Dvorak, M., & Kolmogorov, V. (n.d.). Generalized minimum 0-extension problem and discrete convexity. arXiv.
Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” ArXiv, n.d.
M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” arXiv. .
Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv, 2109.10203.
Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” ArXiv, 2109.10203.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2021-09-27
MD5 Checksum
e7e83065f7bc18b9c188bf93b5ca5db6


Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 2109.10203

Search this title in

Google Scholar