test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works
       

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9459

Title: Random constraint satisfaction: A more accurate picture
Authors: Molloy, M.
Achlioptas, D.
Kirousis, L.
Krizanc, D.
Kranakis, E.
Keywords: constraint satisfaction
random graphs
threshold phenomena
phase transitions
Issue Date: 2001
Publisher: Springer
Citation: Achlioptas, D., Molloy, M. S. O., Kirousis, L. M., Stamatiou, Y. C., Kranakis, E., & Krizanc, D. (2001). Random constraint satisfaction: A more accurate picture. Constraints, 6(4), 329-344.
Abstract: In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly, experimental results with various models for generating random CSP instances suggest that the probability of such problems having a solution exhibits a "threshold-like" behavior. In this spirit, some preliminary theoretical work has been done in analyzing these models asymptotically, i.e., as the number of variables grows. In this paper we prove that, contrary to beliefs based on experimental evidence, the models commonly used for generating random CSP instances do not have an asymptotic threshold. In particular, we prove that asymptotically almost all instances they generate are overconstrained, suffering from trivial, local inconsistencies. To complement this result we present an alternative, single-parameter model for generating random CSP instances and prove that, unlike current models, it exhibits non-triv ial asymptotic behavior. Moreover, for this new model we derive explicit bounds for the narrow region within which the probability of having a solution changes dramatically.
Description: http://www.springerlink.com/content/k273822u717ph566/ The original publication is available at http://www.springerlink.com
URI: http://hdl.handle.net/1807/9459
ISSN: 1572-9354
Rights: IMPORTANT NOTICE: TO USERS OF THIS DATA ALL DATA WAS COLLECTED THROUGH THE CONSIDERABLE EFFORTS OF THE RESEARCHERS CONTRIBUTING TO IT. WHILE THE DATA CAN BE USED FOR NEW ANALYSES, Contact should be main to the collector of this data prior to publication and ACKNOWLEDGEMENT MUST BE EXPLICITLY MADE AS TO THE COLLECTOR AND CONTRIBUTOR OF THESE DATA.
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
post print-random constraint satisfaction.pdf272.2 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

uoft