- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On uniform sampling of cliques
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
On uniform sampling of cliques khorvash, Massih
Abstract
The 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.
Item Metadata
Title |
On uniform sampling of cliques
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2009
|
Description |
The 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.
|
Extent |
816908 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-10-15
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0051700
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2009-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International