A Note on Valid Inequalities for PageRank Optimization with Edge Selection Constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909428458979328 |
|---|---|
| author | Yang, Shang-Ru Liao, Yung-Han Chien, Chih-Ching Wu, Hao-Hsiang |
| author_facet | Yang, Shang-Ru Liao, Yung-Han Chien, Chih-Ching Wu, Hao-Hsiang |
| contents | Csáji, Jungers, and Blondel prove that while a PageRank optimization problem with edge selection constraints is NP-hard, it can be solved optimally in polynomial time for the unconstrained case. This theoretical result is accompanied by several observations, which we leverage to develop valid inequalities in polynomial time for this class of NP-hard problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11071 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Note on Valid Inequalities for PageRank Optimization with Edge Selection Constraints Yang, Shang-Ru Liao, Yung-Han Chien, Chih-Ching Wu, Hao-Hsiang Optimization and Control Csáji, Jungers, and Blondel prove that while a PageRank optimization problem with edge selection constraints is NP-hard, it can be solved optimally in polynomial time for the unconstrained case. This theoretical result is accompanied by several observations, which we leverage to develop valid inequalities in polynomial time for this class of NP-hard problems. |
| title | A Note on Valid Inequalities for PageRank Optimization with Edge Selection Constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.11071 |