Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2011.08447 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912752530882560 |
|---|---|
| author | Khanna, Yash |
| author_facet | Khanna, Yash |
| contents | In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [16] which has been studied in many other works [8,11,17,26,35,38] for a variety of graph problems. Our algorithm and analysis is on similar lines to the one studied for the Densest $k$-subgraph problem in the work of Khanna and Louis [25].
As a by-product of our main result, we give an alternate SDP-based rounding algorithm (with similar guarantees) for solving the Planted Clique problem in a random graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_08447 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Exact recovery of planted cliques in semi-random graphs Khanna, Yash Data Structures and Algorithms In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [16] which has been studied in many other works [8,11,17,26,35,38] for a variety of graph problems. Our algorithm and analysis is on similar lines to the one studied for the Densest $k$-subgraph problem in the work of Khanna and Louis [25]. As a by-product of our main result, we give an alternate SDP-based rounding algorithm (with similar guarantees) for solving the Planted Clique problem in a random graph. |
| title | Exact recovery of planted cliques in semi-random graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2011.08447 |