Zobrazeno 1 - 10
of 156
pro vyhledávání: '"Kirk Pruhs"'
Autor:
Nikhil Bansal, Kirk Pruhs
Publikováno v:
Journal of Computational Geometry, Vol 7, Iss 1 (2016)
We give a randomized polynomial time algorithm with approximation ratio $O(\log \phi(n))$ for weighted set multi-cover instances with a shallow cell complexity of at most $f(z,k) =z\phi(z) k^{O(1)}$. Up to constant factors, this matches a recent resu
Externí odkaz:
https://doaj.org/article/a3a530036b3342deb5f53faee2370437
We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements can be partitioned into sets $X_1, X_2, \ldots, X_l$ with the following
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f49cea72eb95b30c027042d9d70ae02
http://arxiv.org/abs/2206.12896
http://arxiv.org/abs/2206.12896
Publikováno v:
Operations Research Letters. 49:17-22
We consider the matroid intersection cover problem. This is a special case of set cover where the sets are derived from the intersection of matroids. We introduce a technique for computing matroid intersection covers. We give polynomial-time algorith
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d199c32e575cfe2c35ffa4158e569db5
https://doi.org/10.1016/j.orl.2020.11.003
https://doi.org/10.1016/j.orl.2020.11.003
Autor:
Viswanath Nagarajan, Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Cliff Stein, Kirk Pruhs
Publikováno v:
SIAM Journal on Computing. 49:37-66
We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components that are speed scalable, and that may be shut down when idle. We assume the standard ...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c14120ff36f7c8905af53e1064c73aac
https://doi.org/10.1137/18m1228591
https://doi.org/10.1137/18m1228591
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783031069000
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::12d1b55678d3908f8c00faf2c9529576
https://doi.org/10.1007/978-3-031-06901-7_30
https://doi.org/10.1007/978-3-031-06901-7_30
Publikováno v:
ACM Transactions on Embedded Computing Systems. 18:1-19
PIM (processing-in-memory) based hardware accelerators have shown great potentials in addressing the computation and memory access intensity of modern CNNs (convolutional neural networks). While adopting NVM (non-volatile memory) helps to further mit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::90f4a0cbee58acf27d9de3caed4154a3
https://doi.org/10.1145/3358199
https://doi.org/10.1145/3358199
Publikováno v:
Algorithmica. 81:2917-2933
Online matching on a line involves matching an online stream of requests to a given set of servers, all in the real line, with the objective of minimizing the sum of the distances between matched server-request pairs. The best previously known upper
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f54baaeda3caa556c793bcdc7ca25065
https://doi.org/10.1007/s00453-019-00565-w
https://doi.org/10.1007/s00453-019-00565-w
Publikováno v:
APOCS
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2e5188ebbfee179d844dda501bee25f6
https://doi.org/10.1137/1.9781611976489.8
https://doi.org/10.1137/1.9781611976489.8
Publikováno v:
Fundamentals of Computation Theory ISBN: 9783030865924
FCT
FCT
Motivated by demand-responsive parking pricing systems we consider posted-price algorithms for the online metrical matching problem. Our main result is a polylog competitive posted-price algorithm in the case that the metric space is a spider.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6c87bc18b98ff679a71e605429edbcbd
https://doi.org/10.1007/978-3-030-86593-1_5
https://doi.org/10.1007/978-3-030-86593-1_5