15 citations · 18 across the 4 of their papers we have counts for
4 papers
Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing
David Arthur, Steve Y. Oudot
We investigate the problem of finding reverse nearest neighbors efficiently. Although provably good solutions exist for this problem in low or fixed dimensions, to this date the me…
The Complexity of Flood Filling Games
Raphael Clifford, Markus Jalsenius, Ashley Montanaro +1
We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n by n board of tiles where each tile is allocated one o…
k-Means has Polynomial Smoothed Complexity
David Arthur, Bodo Manthey, Heiko Röglin
The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential wors…
Pricing strategies for viral marketing on Social Networks
David Arthur, Rajeev Motwani, Aneesh Sharma +1
We study the use of viral marketing strategies on social networks to maximize revenue from the sale of a single product. We propose a model in which the decision of a buyer to buy…