Budget-Smoothed Analysis for Submodular Maximization
The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a $1-1/e$ factor. Although it is well known that this guarantee is essentially tight in the worst case -- for greedy and in fact any effici...
Αποθηκεύτηκε σε:
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | Άρθρο |
| Έκδοση: |
2021
|
| Θέματα: | |
| Διαθέσιμο Online: | https://arxiv.org/abs/2102.05782 http://arxiv.org/abs/2102.05782 |
| Ετικέτες: |
Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!
|