Enhanced algorithms for local search

DOI10.1016/J.IPL.2005.11.004MaRDI QIDQ1045925zbMATH OpenOpenAlexFDO

Authors Yves F. Verhoeven

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0506019

zbMATH Keywords

algorithmsanalysis of algorithmsgraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: Let G=(V,E) be a finite graph, and f:V->N be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity O(log n)cdot d+O(sqrt{g})cdotsqrt{n}, so that we obtain a deterministic query complexity of d+O(sqrt{g})cdotsqrt{n}, where n is the size of G, d is its maximum degree, and $g$ is its genus. We also give a quantum version of our algorithm, whose query complexity is of O(sqrt{d})+O(sqrt[4]{g})cdotsqrt[4]{n}loglog n. Our deterministic and quantum algorithms have query complexities respectively smaller than the generic algorithms of Aldous and of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs. Independently from this work, Zhang has recently given a quantum algorithm which finds a local minimum on the planar grid over {1,...,sqrt{n}}^2 using O(sqrt[4]{n}(loglog n)^2) queries. Our quantum algorithm can be viewed as a strongly generalized, and slightly enhanced version of this algorithm.

Recommendations

• Quantum and classical query complexities of local search are polynomially related
• Tight bounds for randomized and quantum local search
• New upper and lower bounds for randomized and quantum local search
• Quantum and classical query complexities of local search are polynomially related
• Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

Cites work

• A separator theorem for graphs of bounded genus
• Dividing and conquering the square
• How easy is local search?
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Local optimization on graphs
• Lower bounds for local search by quantum arguments
• Minimization algorithms and random walk on the d-cube
• Quantum and classical query complexities of local search are polynomially related
• Quantum lower bounds by polynomials

Cited in

(8)

• Mechanisms for local search
• Finding robust solutions using local search
• Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
• scientific article; zbMATH DE number 1082101 (Why is no real title available?)
• On the minimum degree up to local complementation: bounds and complexity
• Quantum and classical query complexities of local search are polynomially related
• The randomized query complexity of finding a Tarski fixed point on the Boolean hypercube
• On the quantum query complexity of local search in two and three dimensions

This page was built for publication: Enhanced algorithms for local search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045925)