nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.07.2016

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

verfasst von: Wei Xu, Fuzhou Gong

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The performances of two types of pure random walk (PRW) algorithms for a model of constraint satisfaction problem with growing domains (called Model RB) are investigated. Threshold phenomenons appear for both algorithms. In particular, when the constraint density \(r\) is smaller than a threshold value \(r_d\), PRW algorithms can solve instances of Model RB efficiently, but when \(r\) is bigger than the \(r_d\), they fail. Using a physical method, we find out the threshold values for both algorithms. When the number of variables \(N\) is large, the threshold values tend to zero, so generally speaking PRW does not work on Model RB. By performing experiments, we show that PRW strategy cannot do better than other fundamental strategies.

Vorheriger Artikel Dynamic matchings in left vertex weighted convex bipartite graphs

Nächster Artikel Kernelization and randomized Parameterized algorithms for Co-path Set problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Achlioptas D, Kirousis L, Kranakis E, Krizanc D, Molloy M, Stamatiou Y (1997) Random constraint satisfaction: a more accurate picture. In: Proceedings of CP. pp 107–120

Alekhnovich M, Ben-Sasson E (2006) Linear upper bounds for random walk on small density random 3-cnfs. SIAM J Comput 36(5):1248–1263MathSciNetCrossRefMATH

Alphonse E, Osmani A (2008) A model to study phase transition and plateaus in relational learning. In: Proceedings of of ILP. pp 6–23

Barthel W, Hartmann AK, Weigt M (2003) Solving satisfiability problems by fluctuations: the dynamics of stochastic local search algorithms. Phys Rev E 67:066104CrossRef

Broder AZ, Frieze AM, Upfal E (1993) On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proceedings of SODA. pp 322–330

Chao M, Franco J (1986) Probabilistic analysis of two heuristics for the 3-satisfiability problem. SIAM J Comput 15(4):1106–1118MathSciNetCrossRefMATH

Coja-Oghlan A, Frieze A (2012) Analyzing Walksat on random formulas. In: Proceedings of ANALCO. pp 48–55

Coja-Oghlan A, Feige U, Frieze A, Krivelevich M, Vilenchik D (2009) On smoothed \(k\)-CNF formulas and the Walksat algorithm. In: Proceedings of SODA. pp 451–460

Fan Y, Shen J (2011) On the phase transitions of random k-constraint satisfaction problems. Artif Intell 175:914–927MathSciNetCrossRefMATH

Fan Y, Shen J, Xu K (2012) A general model and thresholds for random constraint satisfaction problems. Artif Intell 193:1–17MathSciNetCrossRefMATH

Gao Y, Culberson J (2007) Consistency and random constraint satisfaction problems. J Artif Intell Res 28:517–557MathSciNetMATH

Gent I, Macintype E, Prosser P, Smith B, Walsh T (2001) Random constraint satisfaction: flaws and structure. Constraints 6(4):345–372MathSciNetCrossRefMATH

Huang P, Yin MH (2014) An upper (lower) bound for Max (Min) CSP. Sci China Inf Sci 57:072109MathSciNetMATH

Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. In: Proceedings of FAW-AAIM. pp 233–243

Kamath A, Motwani R, Palem K, Spirakis P (1995) Tail bounds for occupancy and the satisfiability threshold conjecture. Random Struct Algorithm 7:59–80MathSciNetCrossRefMATH

Lecoutre C (2009) Constraint networks: techniques and algorithms. Wiley, HobokenCrossRef

Liu T, Lin X, Wang C, Su K, Xu K (2011) Large hinge width on sparse random hypergraphs. In: Proceedings of IJCAI. pp 611–616

Liu T, Wang C, Xu K (2014) Large hypertree width for sparse random hypergraphs. J Comb Optim. doi:10.1007/s10878-013-9704-y

Richter S, Helmert M, Gretton C (2007) A stochastic local search approach to vertex cover. In: Proceedings of KI. pp 412–426

Rossi F, Van Beek P, Walsh T (eds) (2006) Handbook of constraint programming. Elsevier, AmsterdamMATH

Schöning U (2002) A probabilistic algorithm for \(k\)-SAT based on limited local search and restart. Algorithmica 32:615–623MathSciNetCrossRefMATH

Schöning U (1999) A probabilistic algorithm for \(k\)-SAT and constraint satisfaction problems. In: Proceedings of FOCS. pp 410–414

Semerjian G, Monasson R (2004) A study of pure random walk on random satisfiability problems with physical methods. In: Proceedings of SAT. pp 120–134

Semerjian G, Monasson R (2003) Relaxation and metastability in the random walk SAT search procedure. Phys Rev E 67:066103CrossRef

Shen J, Ren Y (2014) Bounding the scaling window of random constraint satisfaction problems. J Comb Optim. doi:10.1007/s10878-014-9789-y

Smith BM (2001) Constructing an asymptotic phase transition in random binary constraint satisfaction problems. Theor Comput Sci 265:265–283MathSciNetCrossRefMATH

Smith BM, Dyer ME (1996) Locating the phase transition in binary constraint satisfaction problems. Artif Intell 81:155–181MathSciNetCrossRef

Wang C, Liu T, Cui P, Xu K (2011) A note on treewidth in random graphs. In: Proceedings of COCOA. pp 491–499

Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res 12:93–103MathSciNetMATH

Xu K, Li W (2006) Many hard examples in exact phase transitions. Theor Comput Sci 355:291–302MathSciNetCrossRefMATH

Xu K, Boussemart F, Hemery F, Lecoutre C (2007) Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell 171:514–534MathSciNetCrossRefMATH

Xu W (2014) An analysis of backtrack-free algorithm on a constraint satisfaction problem with growing domains (in Chineses). Acta Math Appl Sin (Chin Ser) 37(3):385–392MATH

Zhao C, Zheng Z (2011) Threshold behaviors of a random constraint satisfaction problem with exact phase transitions. Inf Process Lett 111:985–988MathSciNetCrossRefMATH

Zhao C, Zhang P, Zheng Z, Xu K (2012) Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains. Phys Rev E 85:016106CrossRef

Zhou G, Gao Z, Liu J (2014) On the constraint length of random k-CSP. J Comb Optim. doi:10.1007/s10878-014-9731-3

Titel: Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
verfasst von: Wei Xu
Fuzhou Gong
Publikationsdatum: 01.07.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9891-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Complete forcing numbers of primitive coronoids

2-Distance coloring of a planar graph without 3, 4, 7-cycles

Algorithms for the workflow satisfiability problem engineered for counting constraints

Computing unique maximum matchings in time for König–Egerváry graphs and unicyclic graphs

A complexity dichotomy and a new boundary class for the dominating set problem

Dynamic matchings in left vertex weighted convex bipartite graphs