Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913561116147712 |
|---|---|
| author | Nath, Ankur Kuhnle, Alan |
| author_facet | Nath, Ankur Kuhnle, Alan |
| contents | Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17945 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization Nath, Ankur Kuhnle, Alan Data Structures and Algorithms Machine Learning Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning. |
| title | Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2410.17945 |