Abstract
dc:descriptionThe problem that we are addressing in this thesis is the problem of sampling uniformly the cliques of a target size k of any given graph. As a natural approach for solving this problem, we used the already available state-of-the-art heuristic MAX-CLIQUE solvers. The heuristic MAX-CLIQUE algorithms, which we used for this task, have k-CLIQUE solvers as their subroutines. This thesis therefore examines how uniformly some of the state-of-the-art stochastic local search MAX-CLIQUE algorithms sample target cliques of graphs, and suggests various methods to improve their sampling performance. We also investigate the limitations of a generic method that uses already existing SAT samplers (such as XORSample and XORSample' [1]) to sample the solutions of the translated SAT instances from k-CLIQUE instances. The main limitation with this method is the huge size of the encoded instances. Another important limitation with this method is that sampling satisfying assignments of the encoded SAT instances is expensive. We found that some state-of-the-art heuristic MAX-CLIQUE algorithms (DLS-MC [2] and PLS [3]) are already able to sample near-uniformly the target cliques of many of the instances used in this thesis. Furthermore, we gained some insights into various properties of these algorithms, which helped us to improve the sampling performance on the remaining instances.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- khorvash, Massih
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/13923