The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #724

Title:Computational Phase Transitions in Real Problems
Authors:Gent,I; Walsh,T
Date:Dec 1994
Presented:Submitted to IJCAI-95
Abstract:We examine phase transitions in real computational problems using a wide variety of algorithms. These phase transitions resemble those observed with randomly generated problems. Real problems do, however, contain new features (for example, large scale structures rare in random problems) which can make them significantly harder than random problems. Our results suggest a new methodology for benchmarking algorithms. in addition, they help to identify the location of the really hard real problems.

[Search These Pages] [DAI Home Page] [Comment]