h1

000462250 001__ 462250
000462250 005__ 20231017144437.0
000462250 0247_ $$2URN$$aurn:nbn:de:hbz:82-rwth-2015-004945
000462250 0247_ $$2HBZ$$aHT018589377
000462250 0247_ $$2Laufende Nummer$$a34662
000462250 037__ $$aRWTH-2015-00494
000462250 041__ $$aEnglish
000462250 082__ $$a004
000462250 1001_ $$0P:(DE-82)126900$$aBerkholz, Christoph$$b0
000462250 245__ $$aLower Bounds for Heuristic Algorithms$$cvorgelegt von Christoph Berkholz$$honline, print
000462250 246_3 $$aUntere Schranken für heuristische Algorithmen$$yGerman
000462250 260__ $$aAachen$$bPublikationsserver der RWTH Aachen University$$c2014
000462250 260__ $$c2015
000462250 300__ $$a169 S. : graph. Darst.
000462250 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000462250 3367_ $$02$$2EndNote$$aThesis
000462250 3367_ $$2DRIVER$$adoctoralThesis
000462250 3367_ $$2BibTeX$$aPHDTHESIS
000462250 3367_ $$2DataCite$$aOutput Types/Dissertation
000462250 3367_ $$2ORCID$$aDISSERTATION
000462250 502__ $$aAachen, Techn. Hochsch., Diss., 2014$$gFak01$$o2014-12-04
000462250 500__ $$aPrüfungsjahr: 2014. - Publikationsjahr: 2015
000462250 5203_ $$aFür das Constraint-Satisfaction-Problem (CSP), das Erfüllbarkeitsproblem der Aussagenlogik und das Graphisomorphieproblem sind keine effizienten Algorithmen bekannt.Um sie zu lösen werden deshalb heuristische Algorithmen mit polynomieller Laufzeit eingesetzt. In der vorliegenden Dissertation werden drei klassische Heuristiken für die genannten Entscheidungsprobleme dahingehend untersucht, ob sie mit schnelleren als den bekannten Algorithmen implementiert werden können.Die k-Konsistenz-Heuristik für das CSP versucht durch sukzessives Ableiten neuer Bedingungen lokal konsistente Instanzen zu erzeugen und kann mit einer Laufzeit von O(n^{2k}) implementiert werden.Wir zeigen, dass der Anstieg der Laufzeit mit wachsendem Parameter k unvermeidbar ist. Dazu beweisen wir für eine absolute Konstante c>0, dass es nicht möglich ist in Zeit O(n^{ck}) zu entscheiden, ob lokale Konsistenz auf einer binären CSP-Instanz erreicht werden kann.Weiterhin untersuchen wir den Ableitungsprozess, der k-Konsistenz-Algorithmen zugrunde liegt, und beweisen eine optimale untere Schranke an die Anzahl der sequentiell abhängigen Ableitungsschritte. Eine Heuristik für das aussagenlogische Erfüllbarkeitsproblem ist das Suchen nach einer Resolutionswiderlegung, in der jede Klausel höchstens k Literale enthält. Eine solche Resolutionswiderlegung der Weite k kann von einem einfachen Suchalgorithmus in Zeit O(n^(k+1)) gefunden werden.Wir zeigen für eine absolute Konstante c>0, dass es unmöglich ist in Zeit O(n^(ck)) zu entscheiden, ob eine Resolutionswiderlegung der Weite k existiert.Die beiden unteren Schranken an die Laufzeit für lokale Konsistenz und Resolution beschränkter Weite kommen ohne komplexitätstheoretische Annahmen aus und verdeutlichen eine der wenigen Anwendung des  Zeithierarchiesatzes  auf natürliche Entscheidungsprobleme.Der naive Klassifizierungsalgorithmus für das Graphisomorphieproblem berechnet eine stabile Färbung der Knotenmenge eines Graphen durch iteratives Verfeinern der Farbklassen.Durch geschickte Auswahl der zu verfeinernden Farbklassen kann das Verfahren auf zusammenhängenden Graphen mit n Knoten und m Kanten mit einer Laufzeit von O(m log(n)) implementiert werden. Wir zeigen, dass dieses Vorgehen optimal ist und konstruieren dazu eine Familie von Graphen auf der jede Sequenz von Verfeinerungen m log(n) Berechnungsschritte benötigt.$$lger
000462250 520__ $$aThe 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.$$leng
000462250 591__ $$aGermany
000462250 653_7 $$aInformatik
000462250 7001_ $$0P:(DE-82)IDM00084$$aGrohe, Martin$$b1$$eThesis advisor
000462250 7001_ $$0P:(DE-82)018108$$aOtto, Martin$$b2$$eThesis advisor
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250.pdf$$yOpenAccess
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250_source.zip$$yRestricted
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250.gif?subformat=icon$$xicon$$yOpenAccess
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000462250 8564_ $$uhttps://publications.rwth-aachen.de/record/462250/files/462250.pdf?subformat=pdfa$$xpdfa$$yOpenAccess
000462250 909CO $$ooai:publications.rwth-aachen.de:462250$$pdnbdelivery$$pVDB$$pdriver$$purn$$popen_access$$popenaire
000462250 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000462250 9141_ $$y2014
000462250 9201_ $$0I:(DE-82)122110_20140620$$k122110$$lLehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme)$$x0
000462250 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000462250 961__ $$c2015-02-01T20:59:32.712582$$x2015-02-01T20:59:32.712582$$z2015-03-11
000462250 970__ $$aHT018589377
000462250 9801_ $$aFullTexts
000462250 980__ $$aphd
000462250 980__ $$aUNRESTRICTED
000462250 980__ $$aVDB
000462250 980__ $$aI:(DE-82)122110_20140620
000462250 980__ $$aI:(DE-82)120000_20140620