Paper by Erik D. Demaine
- Erik D. Demaine and Stefan Langerman, “Optimizing a 2D Function Satisfying Unimodality Properties”, in Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science, volume 3669, Mallorca, Spain, October 3–6, 2005, pages 887–898.
The number of probes needed by the best possible algorithm for locally or
globally optimizing a bivariate function varies substantially depending on
the assumptions made about the function. We consider a wide variety of
assumptions—in particular, global unimodality, unimodality of rows and/or
columns, and total unimodality—and prove tight or nearly tight upper and
lower bounds in all cases. Our results include both nontrivial optimization
algorithms and nontrivial adversary arguments depending on the scenario.
- This paper is also available from SpringerLink.
- Copyright held by the authors.
- The paper is 12 pages.
- The paper is available in PostScript (388k), gzipped PostScript (151k), and PDF (202k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- UnimodalOptimization_EuroCG2004 (Optimizing a 2D Function Satisfying Unimodality Properties)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 18, 2020 by