ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915295002624000 |
|---|---|
| author | Gallart, Joan Vendrell Kuhnle, Alan Kia, Solmaz |
| author_facet | Gallart, Joan Vendrell Kuhnle, Alan Kia, Solmaz |
| contents | This paper introduces Rewired Sequential Greedy (ResQue Greedy), an enhanced approach for submodular maximization under cardinality constraints. By integrating a novel set curvature metric within a lattice-based framework, ResQue Greedy identifies and corrects suboptimal decisions made by the standard sequential greedy algorithm. Specifically, a curvature-aware rewiring strategy is employed to dynamically redirect the solution path, leading to improved approximation performance over the conventional sequential greedy algorithm without significantly increasing computational complexity. Numerical experiments demonstrate that ResQue Greedy achieves tighter near-optimality bounds compared to the traditional sequential greedy method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13670 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization Gallart, Joan Vendrell Kuhnle, Alan Kia, Solmaz Discrete Mathematics Data Structures and Algorithms Optimization and Control This paper introduces Rewired Sequential Greedy (ResQue Greedy), an enhanced approach for submodular maximization under cardinality constraints. By integrating a novel set curvature metric within a lattice-based framework, ResQue Greedy identifies and corrects suboptimal decisions made by the standard sequential greedy algorithm. Specifically, a curvature-aware rewiring strategy is employed to dynamically redirect the solution path, leading to improved approximation performance over the conventional sequential greedy algorithm without significantly increasing computational complexity. Numerical experiments demonstrate that ResQue Greedy achieves tighter near-optimality bounds compared to the traditional sequential greedy method. |
| title | ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization |
| topic | Discrete Mathematics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2505.13670 |