13 citations · 38 across the 6 of their papers we have counts for
7 papers
Algorithms and Improved bounds for online learning under finite hypothesis class
Ankit Sharma, Late C. A. Murthy
Online learning is the process of answering a sequence of questions based on the correct answers to the previous questions. It is studied in many research areas such as game theory…
Leveraging web resources for keyword assignment to short text documents
Ayush Singhal, Ravindra Kasturi, Ankit Sharma +1
Assigning relevant keywords to documents is very important for efficient retrieval, clustering and management of the documents. Especially with the web corpus deluged with digital…
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Avrim Blum, John P. Dickerson, Nika Haghtalab +3
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic -s…
Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
Ankit Sharma, Jan Vondrák
We design new approximation algorithms for the Multiway Cut problem, improving the previously known factor of 1.32388 [Buchbinder et al., 2013]. We proceed in three steps. First, w…
On the Approximation of Submodular Functions
Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz +2
Submodular functions are a fundamental object of study in combinatorial optimization, economics, machine learning, etc. and exhibit a rich combinatorial structure. Many subclasses…
Welfare and Profit Maximization with Production Costs
Avrim Blum, Anupam Gupta, Yishay Mansour +1
Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired obje…