|
|||||
|
|
A strongly polynomial algorithm for line search in submodular polyhedra |
|
| Authors: | Kiyohito Nagano |
| Institution: | aDepartment of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Bunkyo-ku, Tokyo 113-8656, Japan |
| Abstract: | A submodular polyhedron is a polyhedron associated with a submodular function. This paper presents a strongly polynomial time algorithm for line search in submodular polyhedra with the aid of a fully combinatorial algorithm for submodular function minimization. The algorithm is based on the parametric search method proposed by Megiddo. |
| Keywords: | Submodular function Network flow Exchange capacity |
| 本文献已被 ScienceDirect 等数据库收录！ | |