Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

This paper is also available from SpringerLink.

Copyright:

Copyright held by the authors.

Length:

The paper is 12 pages.

Availability:

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)