18 citations · 101 across the 20 of their papers we have counts for
Showing 2013 · cs.DSShow all
3 papers · 2 filters
cs.DS2013★ 9 cited
Approximation Algorithms for Bayesian Multi-Armed Bandit Problems
Sudipto Guha, Kamesh Munagala
In this paper, we consider several finite-horizon Bayesian multi-armed bandit problems with side constraints which are computationally intractable (NP-Hard) and for which no optima…
cs.DS2013★ 17 cited
Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
Kook Jin Ahn, Sudipto Guha
In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number…
cs.DS2013
Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b--Matching Problems in Nonbipartite Graphs
Kook Jin Ahn, Sudipto Guha
We present the first near optimal approximation schemes for the maximum weighted (uncapacitated or capacitated) --matching problems for non-bipartite graphs that run in time (ne…