Discrete Convex Functions on Graphs and Their Algorithmic Applications
Discrete Convex Functions on Graphs and Their Algorithmic Applications
复制标题
图上的离散凸函数及其算法应用
DOI：
10.1007/978-981-10-6147-9_4
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Hirai Hiroshi
中科院分区：
文献类型：
--
作者：
Bruno F. Lourenco;Masakazu Muramatsu;Takashi Tsuchiya;Mituhiro Fukuda;Hirai Hiroshi
本文阐述了作者近年来发展的关于某些图结构上的离散凸函数的理论。该理论是Murota离散凸分析的衍生物，其动机是多流问题中的组合对偶和图上设施定位问题的复杂性分类。我们概述了组合优化问题的理论和算法应用。
The present article is an exposition of a theory of discrete convex functions on certain graph structures, developed by the author in recent years. This theory is a spin-off of discrete convex analysis by Murota, and is motivated by combinatorial dualities in multiflow problems and the complexity classification of facility location problems on graphs. We outline the theory and algorithmic applications in combinatorial optimization problems.