Automatically assigned DDC number: 006333
Manually assigned DDC number: 005116
Number of references: 16
Title: Backbone Fragility Causes the Local Search Cost Peak
Author:
Author:
Subject: Josh Singer,Ian P. Gent Backbone Fragility Causes the Local Search Cost Peak
Description: The local search algorithm Wsat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of Wsat on high-cost random instances, using the recent concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in Wsat's search. This pattern leads us to introduce a measure of the backbone f...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1970-01-01
Pubyear: 1999
Format: ps
Identifier: http://citeseer.ist.psu.edu/276270.html
Source: http://www.cs.strath.ac.uk/~apes/reports/apes-17-1999.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/152657.html" Type="inproceedings" CiteSeer_Book="Principles and Practice of Constraint Programming" CiteSeer_Volume="" Title="Using {CSP} Look-Back Techniques to Solve Exceptionally Hard {SAT} Instances,">
<identifier Org="ISBN:0262510952" Paper_ID="/152657.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0262511126" Paper_ID="/152657.html" Extracted="0262511126" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0444527265" Paper_ID="/152657.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0821804790" Paper_ID="/152657.html" Extracted="0821804790" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1402045522" Paper_ID="/152657.html" Extracted="1402045522" />
<identifier Org="ISBN:1402073208" Paper_ID="/152657.html" Extracted="1402073208" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1558604804" Paper_ID="/152657.html" Extracted="1558604804" />
<identifier Org="ISBN:1586039253" Paper_ID="/152657.html" Extracted="1586039253" />
<identifier Org="ISBN:1595931619" Paper_ID="/152657.html" Extracted="1595931619" DDC="003" Normalized_DDC="003" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1841500585" Paper_ID="/152657.html" Extracted="1841500585" />
<identifier Org="ISBN:3540009868" Paper_ID="/152657.html" Extracted="3540009868" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540410538" Paper_ID="/152657.html" Extracted="3540410538" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540427333" Paper_ID="/152657.html" Extracted="3540427333" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540637532" Paper_ID="/152657.html" Extracted="3540637532" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540652248" Paper_ID="/152657.html" Extracted="3540652248" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540859578" Paper_ID="/152657.html" Extracted="3540859578" />
</rec>
<rec ID="/109578.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Twelfth International Joint Conference on Artificial Intelligence IJCAI91 Sidney Australia" CiteSeer_Volume="" Title="{Where the Really Hard Problems Are},">
<identifier Org="ISBN:019517738X" Paper_ID="/109578.html" Extracted="019517738X" DDC="511.3/52" Normalized_DDC="511352" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0262510715" Paper_ID="/109578.html" Extracted="0262510715" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0262510987" Paper_ID="/109578.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0762303050" Paper_ID="/109578.html" Extracted="0762303050" DDC="363.738747" Normalized_DDC="363738747" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1558604804" Paper_ID="/109578.html" Extracted="1558604804" />
<identifier Org="ISBN:1586030132" Paper_ID="/109578.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1586036424" Paper_ID="/109578.html" Extracted="1586036424" />
<identifier Org="ISBN:3540213678" Paper_ID="/109578.html" Extracted="3540213678" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540410945" Paper_ID="/109578.html" Extracted="3540410945" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540584676" Paper_ID="/109578.html" Extracted="3540584676" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540594795" Paper_ID="/109578.html" Extracted="3540594795" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540637532" Paper_ID="/109578.html" Extracted="3540637532" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540650784" Paper_ID="/109578.html" Extracted="3540650784" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540668225" Paper_ID="/109578.html" Extracted="3540668225" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540751181" Paper_ID="/109578.html" Extracted="3540751181" />
<identifier Org="ISBN:9051992165" Paper_ID="/109578.html" Extracted="9051992165" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
</rec>
<rec ID="/10117.html" Type="inproceedings" CiteSeer_Book="Principles and Practice of Constraint Programming" CiteSeer_Volume="" Title="Local Search and the Number of Solutions,">
<identifier Org="ISBN:0262510952" Paper_ID="/10117.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262511126" Paper_ID="/10117.html" Extracted="0262511126" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:038709623X" Paper_ID="/10117.html" Extracted="038709623X" />
<identifier Org="ISBN:1558608729" Paper_ID="/10117.html" Extracted="1558608729" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1581130961" Paper_ID="/10117.html" Extracted="1581130961" DDC="025.524" Normalized_DDC="025524" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586030132" Paper_ID="/10117.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540208518" Paper_ID="/10117.html" Extracted="3540208518" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540213678" Paper_ID="/10117.html" Extracted="3540213678" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540220046" Paper_ID="/10117.html" Extracted="3540220046" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540230920" Paper_ID="/10117.html" Extracted="3540230920" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540433244" Paper_ID="/10117.html" Extracted="3540433244" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540435441" Paper_ID="/10117.html" Extracted="3540435441" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540637532" Paper_ID="/10117.html" Extracted="3540637532" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354066548X" Paper_ID="/10117.html" Extracted="354066548X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354078294X" Paper_ID="/10117.html" Extracted="354078294X" DDC="511/.6" Normalized_DDC="5116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3638921743" Paper_ID="/10117.html" Extracted="3638921743" />
</rec>
<rec ID="/36470.html" Type="incollection" CiteSeer_Book="Satisfiability Problem Theory and Applications" CiteSeer_Volume="" Title="Finding Hard Instances of the Satisfiability Problem: {A} Survey,">
<identifier Org="ISBN:0821804790" Paper_ID="/36470.html" Extracted="0821804790" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1558604804" Paper_ID="/36470.html" Extracted="1558604804" />
<identifier Org="ISBN:1584883472" Paper_ID="/36470.html" Extracted="1584883472" DDC="510/.3" Normalized_DDC="5103" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1586030132" Paper_ID="/36470.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1586030612" Paper_ID="/36470.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540001972" Paper_ID="/36470.html" Extracted="3540001972" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540075445" Paper_ID="/36470.html" Extracted="3540075445" DDC="004" Normalized_DDC="004" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540202021" Paper_ID="/36470.html" Extracted="3540202021" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540208518" Paper_ID="/36470.html" Extracted="3540208518" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540228497" Paper_ID="/36470.html" Extracted="3540228497" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540230971" Paper_ID="/36470.html" Extracted="3540230971" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540290516" Paper_ID="/36470.html" Extracted="3540290516" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540422544" Paper_ID="/36470.html" Extracted="3540422544" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540678395" Paper_ID="/36470.html" Extracted="3540678395" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540681221" Paper_ID="/36470.html" Extracted="3540681221" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540797181" Paper_ID="/36470.html" Extracted="3540797181" />
<identifier Org="ISBN:3764324295" Paper_ID="/36470.html" Extracted="3764324295" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.06666666666666667" />
</rec>
<rec ID="/709721.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="the Completeness of WalkSAT for 2-SAT," />
<rec ID="/360.html" Type="article" CiteSeer_Book="Journal of Artificial Intelligence Research" CiteSeer_Volume="7" Title="When Gravity Fails: Local Search Topology,">
<identifier Org="ISBN:019517738X" Paper_ID="/360.html" Extracted="019517738X" DDC="511.3/52" Normalized_DDC="511352" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0262510987" Paper_ID="/360.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0262511290" Paper_ID="/360.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0262560976" Paper_ID="/360.html" Extracted="0262560976" DDC="001.4/225/028563" Normalized_DDC="0014225028563" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0792372247" Paper_ID="/360.html" Extracted="0792372247" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1558605592" Paper_ID="/360.html" Extracted="1558605592" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1558608729" Paper_ID="/360.html" Extracted="1558608729" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1586030612" Paper_ID="/360.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540202021" Paper_ID="/360.html" Extracted="3540202021" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540435441" Paper_ID="/360.html" Extracted="3540435441" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540650784" Paper_ID="/360.html" Extracted="3540650784" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
</rec>
<rec ID="/212583.html" Type="inproceedings" CiteSeer_Book="AAAIIAAI Vol 1" CiteSeer_Volume="" Title="The Constrainedness of Search,">
<identifier Org="ISBN:0262510952" Paper_ID="/212583.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0444527265" Paper_ID="/212583.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1558604804" Paper_ID="/212583.html" Extracted="1558604804" />
<identifier Org="ISBN:1586030132" Paper_ID="/212583.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586034561" Paper_ID="/212583.html" Extracted="1586034561" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540207791" Paper_ID="/212583.html" Extracted="3540207791" DDC="005.4/465" Normalized_DDC="0054465" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540213678" Paper_ID="/212583.html" Extracted="3540213678" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:354021836X" Paper_ID="/212583.html" Extracted="354021836X" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540219374" Paper_ID="/212583.html" Extracted="3540219374" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540229590" Paper_ID="/212583.html" Extracted="3540229590" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540232370" Paper_ID="/212583.html" Extracted="3540232370" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540238069" Paper_ID="/212583.html" Extracted="3540238069" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540251766" Paper_ID="/212583.html" Extracted="3540251766" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540428631" Paper_ID="/212583.html" Extracted="3540428631" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540668225" Paper_ID="/212583.html" Extracted="3540668225" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:354068154X" Paper_ID="/212583.html" Extracted="354068154X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:427490525X" Paper_ID="/212583.html" Extracted="427490525X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
</rec>
<rec ID="/460258.html" Type="article" CiteSeer_Book="Journal of Artificial Intelligence Research" CiteSeer_Volume="1" Title="An Empirical Analysis of Search in {GSAT},">
<identifier Org="ISBN:0262510952" Paper_ID="/460258.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262510987" Paper_ID="/460258.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262511126" Paper_ID="/460258.html" Extracted="0262511126" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262511290" Paper_ID="/460258.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262611023" Paper_ID="/460258.html" Extracted="0262611023" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0792380673" Paper_ID="/460258.html" Extracted="0792380673" DDC="005.1/6" Normalized_DDC="00516" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0821804790" Paper_ID="/460258.html" Extracted="0821804790" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1558608729" Paper_ID="/460258.html" Extracted="1558608729" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586030612" Paper_ID="/460258.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540220674" Paper_ID="/460258.html" Extracted="3540220674" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540441204" Paper_ID="/460258.html" Extracted="3540441204" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540617086" Paper_ID="/460258.html" Extracted="3540617086" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540635866" Paper_ID="/460258.html" Extracted="3540635866" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540649921" Paper_ID="/460258.html" Extracted="3540649921" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540663673" Paper_ID="/460258.html" Extracted="3540663673" DDC="519.7/7" Normalized_DDC="51977" Normalized_Weight="0.0625" />
<identifier Org="ISBN:9051992165" Paper_ID="/460258.html" Extracted="9051992165" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
</rec>
<rec ID="/78869.html" Type="article" CiteSeer_Book="Artificial Intelligence" CiteSeer_Volume="81" Title="The Satisfiability Constraint Gap,">
<identifier Org="ISBN:0262510952" Paper_ID="/78869.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1" />
<identifier Org="ISBN:0262510987" Paper_ID="/78869.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1" />
<identifier Org="ISBN:0780359593" Paper_ID="/78869.html" Extracted="0780359593" />
<identifier Org="ISBN:0780366573" Paper_ID="/78869.html" Extracted="0780366573" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1" />
<identifier Org="ISBN:1558604855" Paper_ID="/78869.html" Extracted="1558604855" />
<identifier Org="ISBN:1558607749" Paper_ID="/78869.html" Extracted="1558607749" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.1" />
<identifier Org="ISBN:1586030612" Paper_ID="/78869.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540433465" Paper_ID="/78869.html" Extracted="3540433465" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540440402" Paper_ID="/78869.html" Extracted="3540440402" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540637532" Paper_ID="/78869.html" Extracted="3540637532" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.1" />
<identifier Org="ISBN:9051992165" Paper_ID="/78869.html" Extracted="9051992165" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1" />
<identifier Org="ISBN:9051994176" Paper_ID="/78869.html" Extracted="9051994176" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.1" />
</rec>
<rec ID="/347627.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Sixteenth National Conference on Artificial Intelligence AAAI99" CiteSeer_Volume="" Title="On the Run-Time Behaviour of Stochastic Local Search Algorithms for {SAT},">
<identifier Org="ISBN:0262511126" Paper_ID="/347627.html" Extracted="0262511126" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0262511290" Paper_ID="/347627.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0444527265" Paper_ID="/347627.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0780366573" Paper_ID="/347627.html" Extracted="0780366573" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1558607749" Paper_ID="/347627.html" Extracted="1558607749" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1558608729" Paper_ID="/347627.html" Extracted="1558608729" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:157735236X" Paper_ID="/347627.html" Extracted="157735236X" />
<identifier Org="ISBN:1584885505" Paper_ID="/347627.html" Extracted="1584885505" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1586030132" Paper_ID="/347627.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1586030612" Paper_ID="/347627.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1586036424" Paper_ID="/347627.html" Extracted="1586036424" />
<identifier Org="ISBN:3540202021" Paper_ID="/347627.html" Extracted="3540202021" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:354027829X" Paper_ID="/347627.html" Extracted="354027829X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540403000" Paper_ID="/347627.html" Extracted="3540403000" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540441204" Paper_ID="/347627.html" Extracted="3540441204" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540769269" Paper_ID="/347627.html" Extracted="3540769269" />
<identifier Org="ISBN:3540894381" Paper_ID="/347627.html" Extracted="3540894381" />
</rec>
<rec ID="/690790.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Fourteenth National Conference on Artificial Intelligence AAAI97" CiteSeer_Volume="" Title="Evidence for Invariants in Local Search,">
<identifier Org="ISBN:0262510952" Paper_ID="/690790.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0444527265" Paper_ID="/690790.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586030132" Paper_ID="/690790.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586030612" Paper_ID="/690790.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586036424" Paper_ID="/690790.html" Extracted="1586036424" />
<identifier Org="ISBN:3540223436" Paper_ID="/690790.html" Extracted="3540223436" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540261524" Paper_ID="/690790.html" Extracted="3540261524" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354027829X" Paper_ID="/690790.html" Extracted="354027829X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540292381" Paper_ID="/690790.html" Extracted="3540292381" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540406778" Paper_ID="/690790.html" Extracted="3540406778" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540426019" Paper_ID="/690790.html" Extracted="3540426019" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540435441" Paper_ID="/690790.html" Extracted="3540435441" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540441204" Paper_ID="/690790.html" Extracted="3540441204" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540441271" Paper_ID="/690790.html" Extracted="3540441271" />
<identifier Org="ISBN:354066131X" Paper_ID="/690790.html" Extracted="354066131X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540664920" Paper_ID="/690790.html" Extracted="3540664920" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540769269" Paper_ID="/690790.html" Extracted="3540769269" />
<identifier Org="ISBN:3540797181" Paper_ID="/690790.html" Extracted="3540797181" />
<identifier Org="ISBN:3540894381" Paper_ID="/690790.html" Extracted="3540894381" />
</rec>
<rec ID="/22312.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Tenth National Conference on Artificial Intelligence" CiteSeer_Volume="" Title="Hard and Easy Distributions for {SAT} Problems,">
<identifier Org="ISBN:012443861X" Paper_ID="/22312.html" Extracted="012443861X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0387776095" Paper_ID="/22312.html" Extracted="0387776095" DDC="519.62" Normalized_DDC="51962" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1402076533" Paper_ID="/22312.html" Extracted="1402076533" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1558603700" Paper_ID="/22312.html" Extracted="1558603700" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1595930108" Paper_ID="/22312.html" Extracted="1595930108" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540202021" Paper_ID="/22312.html" Extracted="3540202021" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540208518" Paper_ID="/22312.html" Extracted="3540208518" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540290060" Paper_ID="/22312.html" Extracted="3540290060" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540320261" Paper_ID="/22312.html" Extracted="3540320261" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540422544" Paper_ID="/22312.html" Extracted="3540422544" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540635769" Paper_ID="/22312.html" Extracted="3540635769" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540741046" Paper_ID="/22312.html" Extracted="3540741046" DDC="519.5/42" Normalized_DDC="519542" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540767185" Paper_ID="/22312.html" Extracted="3540767185" />
<identifier Org="ISBN:3898384934" Paper_ID="/22312.html" Extracted="3898384934" DDC="006.7/8" Normalized_DDC="00678" Normalized_Weight="0.07692307692307693" />
</rec>
<rec ID="/123202.html" Type="inproceedings" CiteSeer_Book="AAAIIAAI" CiteSeer_Volume="" Title="Clustering at the Phase Transition,">
<identifier Org="ISBN:0262510952" Paper_ID="/123202.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0262510987" Paper_ID="/123202.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0262511290" Paper_ID="/123202.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:038709623X" Paper_ID="/123202.html" Extracted="038709623X" />
<identifier Org="ISBN:157735236X" Paper_ID="/123202.html" Extracted="157735236X" />
<identifier Org="ISBN:1586030132" Paper_ID="/123202.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540001972" Paper_ID="/123202.html" Extracted="3540001972" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540207791" Paper_ID="/123202.html" Extracted="3540207791" DDC="005.4/465" Normalized_DDC="0054465" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540219374" Paper_ID="/123202.html" Extracted="3540219374" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540232370" Paper_ID="/123202.html" Extracted="3540232370" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540428631" Paper_ID="/123202.html" Extracted="3540428631" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.1111111111111111" />
</rec>
<rec ID="/76710.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Thirteenth National Conference on Artificial Intelligence AAAI96" CiteSeer_Volume="" Title="Tuning Local Search for Satisfiability Testing,">
<identifier Org="ISBN:026251091X" Paper_ID="/76710.html" Extracted="026251091X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262510952" Paper_ID="/76710.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262510987" Paper_ID="/76710.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262511126" Paper_ID="/76710.html" Extracted="0262511126" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262511290" Paper_ID="/76710.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0387252665" Paper_ID="/76710.html" Extracted="0387252665" DDC="658.5/3" Normalized_DDC="65853" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1558608729" Paper_ID="/76710.html" Extracted="1558608729" DDC="519.6" Normalized_DDC="5196" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586030132" Paper_ID="/76710.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586030612" Paper_ID="/76710.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540320261" Paper_ID="/76710.html" Extracted="3540320261" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540410538" Paper_ID="/76710.html" Extracted="3540410538" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540441204" Paper_ID="/76710.html" Extracted="3540441204" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540663673" Paper_ID="/76710.html" Extracted="3540663673" DDC="519.7/7" Normalized_DDC="51977" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354066548X" Paper_ID="/76710.html" Extracted="354066548X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="/27077.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Twelfth National Conference on Artificial Intelligence AAAI94" CiteSeer_Volume="" Title="Noise strategies for improving local search,">
<identifier Org="ISBN:0262611023" Paper_ID="/27077.html" Extracted="0262611023" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586030132" Paper_ID="/27077.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586030612" Paper_ID="/27077.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3211249346" Paper_ID="/27077.html" Extracted="3211249346" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540223436" Paper_ID="/27077.html" Extracted="3540223436" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540230920" Paper_ID="/27077.html" Extracted="3540230920" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540232419" Paper_ID="/27077.html" Extracted="3540232419" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540265511" Paper_ID="/27077.html" Extracted="3540265511" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:354027829X" Paper_ID="/27077.html" Extracted="354027829X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540406778" Paper_ID="/27077.html" Extracted="3540406778" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540406999" Paper_ID="/27077.html" Extracted="3540406999" DDC="658.5/3" Normalized_DDC="65853" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540428984" Paper_ID="/27077.html" Extracted="3540428984" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540635866" Paper_ID="/27077.html" Extracted="3540635866" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540648240" Paper_ID="/27077.html" Extracted="3540648240" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540664920" Paper_ID="/27077.html" Extracted="3540664920" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540786031" Paper_ID="/27077.html" Extracted="3540786031" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540789863" Paper_ID="/27077.html" Extracted="3540789863" />
<identifier Org="ISBN:3540859578" Paper_ID="/27077.html" Extracted="3540859578" />
<identifier Org="ISBN:3540894381" Paper_ID="/27077.html" Extracted="3540894381" />
</rec>
<rec ID="/3708.html" Type="inproceedings" CiteSeer_Book="AAAIIAAI" CiteSeer_Volume="" Title="The Constrainedness Knife-Edge,">
<identifier Org="ISBN:019517738X" Paper_ID="/3708.html" Extracted="019517738X" DDC="511.3/52" Normalized_DDC="511352" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0262510987" Paper_ID="/3708.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0444527265" Paper_ID="/3708.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0791801764" Paper_ID="/3708.html" Extracted="0791801764" />
<identifier Org="ISBN:1586030132" Paper_ID="/3708.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1586034561" Paper_ID="/3708.html" Extracted="1586034561" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1586034669" Paper_ID="/3708.html" Extracted="1586034669" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540207791" Paper_ID="/3708.html" Extracted="3540207791" DDC="005.4/465" Normalized_DDC="0054465" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540219374" Paper_ID="/3708.html" Extracted="3540219374" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540229590" Paper_ID="/3708.html" Extracted="3540229590" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540238069" Paper_ID="/3708.html" Extracted="3540238069" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354065965X" Paper_ID="/3708.html" Extracted="354065965X" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.09090909090909091" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Backbone Fragility Causes the Local Search Cost Peak" />
</references_metadata>