Computing approximate roots of monotone functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909123074850816 |
|---|---|
| author | Hollender, Alexandros Lawrence, Chester Segal-Halevi, Erel |
| author_facet | Hollender, Alexandros Lawrence, Chester Segal-Halevi, Erel |
| contents | Given a function f: [a,b] -> R, if f(a) < 0 and f(b)> 0 and f is continuous, the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover, given a value-oracle for f, an approximate root of f can be computed using the bisection method, and the number of required evaluations is polynomial in the number of accuracy digits. The goal of this note is to identify conditions under which this polynomiality result extends to a multi-dimensional function that satisfies the conditions of Miranda's theorem -- the natural multi-dimensional extension of the Intermediate Value Theorem. In general, finding an approximate root might require an exponential number of evaluations even for a two-dimensional function. We show that, if f is two-dimensional and satisfies a single monotonicity condition, then the number of required evaluations is polynomial in the accuracy. For any fixed dimension d, if f is a d-dimensional function that satisfies all d^2-d ``ex-diagonal'' monotonicity conditions (that is, component i of f is monotonically decreasing with respect to variable j for all i!=j), then the number of required evaluations is polynomial in the accuracy. But if f satisfies only d^2-d-2 ex-diagonal conditions, then the number of required evaluations may be exponential in the accuracy. The case of d^2-d-1 ex-diagonal conditions remains unsolved. As an example application, we show that computing approximate roots of monotone functions can be used for approximate envy-free cake-cutting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07333 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Computing approximate roots of monotone functions Hollender, Alexandros Lawrence, Chester Segal-Halevi, Erel Computer Science and Game Theory Numerical Analysis Given a function f: [a,b] -> R, if f(a) < 0 and f(b)> 0 and f is continuous, the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover, given a value-oracle for f, an approximate root of f can be computed using the bisection method, and the number of required evaluations is polynomial in the number of accuracy digits. The goal of this note is to identify conditions under which this polynomiality result extends to a multi-dimensional function that satisfies the conditions of Miranda's theorem -- the natural multi-dimensional extension of the Intermediate Value Theorem. In general, finding an approximate root might require an exponential number of evaluations even for a two-dimensional function. We show that, if f is two-dimensional and satisfies a single monotonicity condition, then the number of required evaluations is polynomial in the accuracy. For any fixed dimension d, if f is a d-dimensional function that satisfies all d^2-d ``ex-diagonal'' monotonicity conditions (that is, component i of f is monotonically decreasing with respect to variable j for all i!=j), then the number of required evaluations is polynomial in the accuracy. But if f satisfies only d^2-d-2 ex-diagonal conditions, then the number of required evaluations may be exponential in the accuracy. The case of d^2-d-1 ex-diagonal conditions remains unsolved. As an example application, we show that computing approximate roots of monotone functions can be used for approximate envy-free cake-cutting. |
| title | Computing approximate roots of monotone functions |
| topic | Computer Science and Game Theory Numerical Analysis |
| url | https://arxiv.org/abs/2310.07333 |