Zobrazeno 1 - 10
of 56
pro vyhledávání: '"Debmalya Panigrahi"'
Publikováno v:
ACM Transactions on Algorithms. 19:1-22
On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: We give an algorithm that runs in \(\widetilde{O}(mn^{2k-2})\) time for finding a minimum k -cut in hypergraphs of ar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c0a706611f8555b79a5818a48e10eeee
https://doi.org/10.1145/3570162
https://doi.org/10.1145/3570162
Publikováno v:
ACM Transactions on Algorithms. 18:1-27
In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b9a070e0a49cc0f41da2e567299bf525
https://doi.org/10.1145/3548774
https://doi.org/10.1145/3548774
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 36:6411-6419
We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bfa1c8d252b9d5d38cfa5c351896bbb9
https://doi.org/10.1609/aaai.v36i6.20592
https://doi.org/10.1609/aaai.v36i6.20592
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2f2579c254b631abdfd68381ba60ed17
https://doi.org/10.1137/1.9781611977554.ch95
https://doi.org/10.1137/1.9781611977554.ch95
Publikováno v:
Proceedings of the 30th International Conference on Advances in Geographic Information Systems.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a6d4bd9949911cb9e2e79546fd00602c
https://doi.org/10.1145/3557915.3560982
https://doi.org/10.1145/3557915.3560982
Publikováno v:
Proceedings of the 2022 International Conference on Management of Data.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0997241a5a932fe51a705232169b2cd7
https://doi.org/10.1145/3514221.3517896
https://doi.org/10.1145/3514221.3517896
Publikováno v:
ACM Transactions on Economics and Computation. 9:1-22
This article studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8c5191c037fd85471932271b1f23b981
https://doi.org/10.1145/3434425
https://doi.org/10.1145/3434425
Autor:
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
Publikováno v:
FOCS
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde O(n\cdot \max(m^{2/3}, n))$ time. This improves on the 30 year old bound of $\tilde O(nm)$ obtained by Hao and Orlin for this pro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8864ab7675c7322ac030774ec70c57fb
https://doi.org/10.1109/focs52979.2021.00113
https://doi.org/10.1109/focs52979.2021.00113
Autor:
Jason Li, Debmalya Panigrahi
Publikováno v:
STOC
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s−t mincuts (and by duality, the values of s−t maxflows) for all pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::42e85adafce32d74cf218fb43289daf6
https://doi.org/10.1145/3406325.3451112
https://doi.org/10.1145/3406325.3451112