More Like this

1. On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness

   Pokutta, S.; Singh, M.; Torrico, A. (June 2020, Thirty-seventh International Conference on Machine Learning)

   It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of 1 − 1/e when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm. In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. We show that the greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties in closely with the faster convergence rates of first order methods for sharp functions in convex optimization. 

   more » « less
2. One Hop Greedy Permutations

   Sheehy, Donald R. (January 2020, Proceedings of the 32nd Canadian Conference on Computational Geometry)

   Keil, Mark; Mondal, Debajyoti (Ed.)

   We adapt and generalize a heuristic for k-center clustering to the permutation case, where every pre x of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required O(n2 log n) time for a fi xed k (i.e. not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in O(n log D
   ) time for metrics sets with spread D. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation. 

   more » « less
3. Combinatorial Stochastic-Greedy Bandit

   Fourati, Fares and (February 2024, AAAI)
4. Combinatorial Stochastic-Greedy Bandit

   https://doi.org/10.1609/aaai.v38i11.29093  

   Fourati, Fares; Quinn, Christopher John; Alouini, Mohamed-Slim; Aggarwal, Vaneet (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We propose a novel combinatorial stochastic-greedy bandit (SGB) algorithm for combinatorial multi-armed bandit problems when no extra information other than the joint reward of the selected set of n arms at each time step t in [T] is observed. SGB adopts an optimized stochastic-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms. Unlike existing methods that explore the entire set of unselected base arms during each selection step, our SGB algorithm samples only an optimized proportion of unselected arms and selects actions from this subset. We prove that our algorithm achieves a (1-1/e)-regret bound of O(n^(1/3) k^(2/3) T^(2/3) log(T)^(2/3)) for monotone stochastic submodular rewards, which outperforms the state-of-the-art in terms of the cardinality constraint k. Furthermore, we empirically evaluate the performance of our algorithm in the context of online constrained social influence maximization. Our results demonstrate that our proposed approach consistently outperforms the other algorithms, increasing the performance gap as k grows. 

   more » « less
5. Rainbow Greedy Matching Algorithms

   Bennett, Patrick; Cooper, Colin; Frieze, Alan (October 2025, Springer-)