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 |
| _version_ | 1826211739425832960 |
|---|---|
| author | Goemans, Michel X Gupta, Swati Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Goemans, Michel X Gupta, Swati Jaillet, Patrick |
| author_sort | Goemans, Michel X |
| collection | MIT |
| description | 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 iterations was known (Iwata 2008). We solve this open problem by providing a quadratic bound of n 2 + O(n log 2 n) on its number of iterations. Our result considerably improves upon the only other known strongly polynomial time algorithm, which is based on Megiddo’s parametric search framework and which requires Õ(n 8 ) submodular function minimizations (Nagano 2007). As a by-product of our study, we prove (tight) bounds on the length of chains of ring families and geometrically increasing sequences of sets, which might be of independent interest. Keywords:
Discrete Newton’s algorithm; Submodular functions; Line search; Ring families; Geometrically increasing sequence of sets; Fractional combinatorial optimization |
| first_indexed | 2024-09-23T15:10:20Z |
| format | Article |
| id | mit-1721.1/115886 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:10:20Z |
| publishDate | 2018 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1158862022-09-29T13:11:08Z Discrete Newton’s Algorithm for Parametric Submodular Function Minimization Goemans, Michel X Gupta, Swati Jaillet, Patrick Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Sloan School of Management Goemans, Michel X Gupta, Swati Jaillet, Patrick 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 iterations was known (Iwata 2008). We solve this open problem by providing a quadratic bound of n 2 + O(n log 2 n) on its number of iterations. Our result considerably improves upon the only other known strongly polynomial time algorithm, which is based on Megiddo’s parametric search framework and which requires Õ(n 8 ) submodular function minimizations (Nagano 2007). As a by-product of our study, we prove (tight) bounds on the length of chains of ring families and geometrically increasing sequences of sets, which might be of independent interest. Keywords: Discrete Newton’s algorithm; Submodular functions; Line search; Ring families; Geometrically increasing sequence of sets; Fractional combinatorial optimization 2018-05-25T13:39:15Z 2018-05-25T13:39:15Z 2017-05 2018-05-21T19:11:05Z Article http://purl.org/eprint/type/ConferencePaper 978-3-319-59249-7 978-3-319-59250-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/115886 Goemans, Michel X. et al. “Discrete Newton’s Algorithm for Parametric Submodular Function Minimization.” Lecture Notes in Computer Science (2017): 212–227 © 2017 Springer International Publishing AG https://orcid.org/0000-0002-0520-1165 https://orcid.org/0000-0003-2305-2949 https://orcid.org/0000-0002-8585-6566 http://dx.doi.org/10.1007/978-3-319-59250-3_18 International Conference on Integer Programming and Combinatorial Optimization Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag Other repository |
| spellingShingle | Goemans, Michel X Gupta, Swati Jaillet, Patrick Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title | Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title_full | Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title_fullStr | Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title_full_unstemmed | Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title_short | Discrete Newton’s Algorithm for Parametric Submodular Function Minimization |
| title_sort | discrete newton s algorithm for parametric submodular function minimization |
| url | 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 |
| work_keys_str_mv | AT goemansmichelx discretenewtonsalgorithmforparametricsubmodularfunctionminimization AT guptaswati discretenewtonsalgorithmforparametricsubmodularfunctionminimization AT jailletpatrick discretenewtonsalgorithmforparametricsubmodularfunctionminimization |