Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141606 | Discrete Optimization | 2007 | 11 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Kiyohito Nagano,