Generalized minimum 0-extension problem and discrete convexity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916097062600704 |
|---|---|
| author | Dvorak, Martin Kolmogorov, Vladimir |
| author_facet | Dvorak, Martin Kolmogorov, Vladimir |
| contents | Given a fixed finite metric space $(V,μ)$, the {\em minimum $0$-extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimize function of the form $\min\limits_{x\in V^n} \sum_i f_i(x_i) + \sum_{ij}c_{ij}μ(x_i,x_j)$ where $c_{ij},c_{vi}$ are given nonnegative costs and $f_i:V\rightarrow \mathbb R$ are functions given by $f_i(x_i)=\sum_{v\in V}c_{vi}μ(x_i,v)$. The computational complexity of ${\tt 0\mbox{-}Ext}[μ]$ has been recently established by Karzanov and by Hirai: if metric $μ$ is {\em orientable modular} then ${\tt 0\mbox{-}Ext}[μ]$ can be solved in polynomial time, otherwise ${\tt 0\mbox{-}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^\natural$-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}μ(x_i,\{u,v\})$ for $\{u,v\}\in F$, where set $F\subseteq\binom{V}{2}$ 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 ${\tt 0\mbox{-}Ext}[μ]$ on orientable modular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_10203 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Generalized minimum 0-extension problem and discrete convexity Dvorak, Martin Kolmogorov, Vladimir Computational Complexity Metric Geometry Given a fixed finite metric space $(V,μ)$, the {\em minimum $0$-extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimize function of the form $\min\limits_{x\in V^n} \sum_i f_i(x_i) + \sum_{ij}c_{ij}μ(x_i,x_j)$ where $c_{ij},c_{vi}$ are given nonnegative costs and $f_i:V\rightarrow \mathbb R$ are functions given by $f_i(x_i)=\sum_{v\in V}c_{vi}μ(x_i,v)$. The computational complexity of ${\tt 0\mbox{-}Ext}[μ]$ has been recently established by Karzanov and by Hirai: if metric $μ$ is {\em orientable modular} then ${\tt 0\mbox{-}Ext}[μ]$ can be solved in polynomial time, otherwise ${\tt 0\mbox{-}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^\natural$-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}μ(x_i,\{u,v\})$ for $\{u,v\}\in F$, where set $F\subseteq\binom{V}{2}$ 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 ${\tt 0\mbox{-}Ext}[μ]$ on orientable modular graphs. |
| title | Generalized minimum 0-extension problem and discrete convexity |
| topic | Computational Complexity Metric Geometry |
| url | https://arxiv.org/abs/2109.10203 |