✦ LIBER ✦

On the complexity of finding a local maximum of functions on discrete planar subsets

✍ Scribed by Anton Mityagin

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 237 KB
Volume: 310
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00426-2

No coin nor oath required. For personal study only.

✦ Synopsis

We study how many values of an unknown integer-valued function f one needs to know in order to ÿnd a local maximum of f. We consider functions deÿned on ÿnite subsets of discrete plane. We prove upper bounds for functions deÿned on rectangles and present lower bounds for functions deÿned on arbitrary domains in terms of the size of the domain and the size of its border.

📜 SIMILAR VOLUMES

On the query complexity of finding a loc

On the query complexity of finding a local maximum point

✍ A.L. Rastsvetaev; L.D. Beklemishev 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 94 KB

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M 1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.

On the complexity of finding even pairs

On the complexity of finding even pairs in planar perfect graphs

✍ Rudini M. Sampaio; Cléudia L. Sales 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 271 KB

A note on the complexity of finding regu

A note on the complexity of finding regular subgraphs

✍ J. Plesník 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 308 KB

On the complexity of finding common appr

On the complexity of finding common approximate substrings

✍ Patricia A. Evans; Andrew D. Smith; H.Todd Wareham 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Problems associated with ÿnding strings that are within a speciÿed Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBST

On the complexity of finding the convex

On the complexity of finding the convex hull of a set of points

✍ Davis Avis 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 281 KB

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib