guest ::
| 001 | 462250 | ||
| 005 | 20231017144437.0 | ||
| 024 | 7 | _ | |2 URN |a urn:nbn:de:hbz:82-rwth-2015-004945 |
| 024 | 7 | _ | |2 HBZ |a HT018589377 |
| 024 | 7 | _ | |2 Laufende Nummer |a 34662 |
| 037 | _ | _ | |a RWTH-2015-00494 |
| 041 | _ | _ | |a English |
| 082 | _ | _ | |a 004 |
| 100 | 1 | _ | |0 P:(DE-82)126900 |a Berkholz, Christoph |b 0 |
| 245 | _ | _ | |a Lower Bounds for Heuristic Algorithms |c vorgelegt von Christoph Berkholz |h online, print |
| 246 | _ | 3 | |a Untere Schranken für heuristische Algorithmen |y German |
| 260 | _ | _ | |a Aachen |b Publikationsserver der RWTH Aachen University |c 2014 |
| 260 | _ | _ | |c 2015 |
| 300 | _ | _ | |a 169 S. : graph. Darst. |
| 336 | 7 | _ | |0 PUB:(DE-HGF)11 |2 PUB:(DE-HGF) |a Dissertation / PhD Thesis |b phd |m phd |
| 336 | 7 | _ | |0 2 |2 EndNote |a Thesis |
| 336 | 7 | _ | |2 DRIVER |a doctoralThesis |
| 336 | 7 | _ | |2 BibTeX |a PHDTHESIS |
| 336 | 7 | _ | |2 DataCite |a Output Types/Dissertation |
| 336 | 7 | _ | |2 ORCID |a DISSERTATION |
| 500 | _ | _ | |a Prüfungsjahr: 2014. - Publikationsjahr: 2015 |
| 502 | _ | _ | |a Aachen, Techn. Hochsch., Diss., 2014 |g Fak01 |o 2014-12-04 |
| 520 | 3 | _ | |a Fü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. |l ger |
| 520 | _ | _ | |a 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. |l eng |
| 591 | _ | _ | |a Germany |
| 653 | _ | 7 | |a Informatik |
| 700 | 1 | _ | |0 P:(DE-82)IDM00084 |a Grohe, Martin |b 1 |e Thesis advisor |
| 700 | 1 | _ | |0 P:(DE-82)018108 |a Otto, Martin |b 2 |e Thesis advisor |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250.pdf |y OpenAccess |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250_source.zip |y Restricted |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250.gif?subformat=icon |x icon |y OpenAccess |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250.jpg?subformat=icon-180 |x icon-180 |y OpenAccess |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250.jpg?subformat=icon-700 |x icon-700 |y OpenAccess |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/462250/files/462250.pdf?subformat=pdfa |x pdfa |y OpenAccess |
| 909 | C | O | |o oai:publications.rwth-aachen.de:462250 |p openaire |p open_access |p urn |p driver |p VDB |p dnbdelivery |
| 914 | 1 | _ | |y 2014 |
| 915 | _ | _ | |0 StatID:(DE-HGF)0510 |2 StatID |a OpenAccess |
| 920 | 1 | _ | |0 I:(DE-82)122110_20140620 |k 122110 |l Lehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme) |x 0 |
| 920 | 1 | _ | |0 I:(DE-82)120000_20140620 |k 120000 |l Fachgruppe Informatik |x 1 |
| 970 | _ | _ | |a HT018589377 |
| 980 | 1 | _ | |a FullTexts |
| 980 | _ | _ | |a phd |
| 980 | _ | _ | |a UNRESTRICTED |
| 980 | _ | _ | |a VDB |
| 980 | _ | _ | |a I:(DE-82)122110_20140620 |
| 980 | _ | _ | |a I:(DE-82)120000_20140620 |
| Library | Collection | CLSMajor | CLSMinor | Language | Author |
|---|