% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Berkholz:462250,
author = {Berkholz, Christoph},
othercontributors = {Grohe, Martin and Otto, Martin},
title = {{L}ower {B}ounds for {H}euristic {A}lgorithms},
address = {Aachen},
publisher = {Publikationsserver der RWTH Aachen University},
reportid = {RWTH-2015-00494},
pages = {169 S. : graph. Darst.},
year = {2014},
note = {Prüfungsjahr: 2014. - Publikationsjahr: 2015; Aachen,
Techn. Hochsch., Diss., 2014},
abstract = {The constraint satisfaction problem, the Boolean
satisfiability problem and the graph isomorphism problem do
not have efficient algorithms.In order to solve these
problems, one utilizes heuristic algorithms of polynomial
running time.The present thesis studies three classical
heuristics for the above-mentioned decision problems and
answers the question whether they can be implemented more
efficient than with the fastest known algorithms.The
k-consistency heuristic for the constraint satisfaction
problem tries to establish local consistency by iteratively
propagating new constraints and can be implemented time
$O(n^(2k)).We$ show that the degree of the polynomial that
bounds the running time has to increase linear in k. To
achieve this, we prove for a fixed constant $c\>0$ that
there is no algorithm of running time $O(n^(ck))$ that
decides whether k-consistency can be
established.Furthermore, we analyze the propagation process
of k-consistency algorithms and prove optimal lower bounds
on the number of nested propagation steps.One heuristic for
the Boolean satisfiability problem is to find resolution
refutations in which every clause contains at most k
literals. Such refutations of width k can be found in time
$O(n^(k+1))$ by a simple search procedure.We show for a
fixed constant $c\>0,$ that it cannot be decided in time
$O(n^(ck))$ whether a given formula has a resolution
refutation of width k.The lower bounds on the time
complexity for k-consistency and bounded width resolution do
not rely on complexity theoretic assumptions and demonstrate
one of the rare examples where the deterministic time
hierarchy theorem can be applied to natural decision
problems. The color refinement heuristic for the graph
isomorphism problem computes a stable coloring of the
vertices of a graph by iteratively refining the color
classes.By refining the color classes in a clever order, the
color refinement procedure can be implemented in time O(m
log(n)) on connected graphs with n vertices and m edges.We
show that this refining strategy is optimal.To prove this,
we construct graphs where every possible order of refining
operations needs at least m log(n) computation steps.},
cin = {122110 / 120000},
ddc = {004},
cid = {$I:(DE-82)122110_20140620$ / $I:(DE-82)120000_20140620$},
typ = {PUB:(DE-HGF)11},
urn = {urn:nbn:de:hbz:82-rwth-2015-004945},
url = {https://publications.rwth-aachen.de/record/462250},
}
guest ::