Discrete Newton’s Algorithm for Parametric Submodular Function Minimization
We consider the line search problem in a submodular polyhedron P (f) ⊆ ℝ n : Given an arbitrary a ∈ ℝ n and x 0 ∈ P (f), compute max{δ: x 0 + δa ∈ P (f)}. The use of the discrete Newton’s algorithm for this line search problem is very natural, but no strongly polynomial bound on its number of ite...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Springer-Verlag
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115886 https://orcid.org/0000-0002-0520-1165 https://orcid.org/0000-0003-2305-2949 https://orcid.org/0000-0002-8585-6566 |