Randomized Greedy Methods for Weak Submodular Sensor Selection with Robustness Considerations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912942832746496 |
|---|---|
| author | Kaya, Ege C. Hibbard, Michael Tanaka, Takashi Topcu, Ufuk Hashemi, Abolfazl |
| author_facet | Kaya, Ege C. Hibbard, Michael Tanaka, Takashi Topcu, Ufuk Hashemi, Abolfazl |
| contents | We study a pair of budget- and performance-constrained weak-submodular maximization problems. For computational efficiency, we explore the use of stochastic greedy algorithms which limit the search space via random sampling instead of the standard greedy procedure which explores the entire feasible search space. We propose a pair of stochastic greedy algorithms, namely, Modified Randomized Greedy (MRG) and Dual Randomized Greedy (DRG) to approximately solve the budget- and performance-constrained problems, respectively. For both algorithms, we derive approximation guarantees that hold with high probability. We then examine the use of DRG in robust optimization problems wherein the objective is to maximize the worst-case of a number of weak submodular objectives and propose the Randomized Weak Submodular Saturation Algorithm (Random-WSSA). We further derive a high-probability guarantee for when Random-WSSA successfully constructs a robust solution. Finally, we showcase the effectiveness of these algorithms in a variety of relevant uses within the context of Earth-observing low Earth orbit satellite constellations which estimate atmospheric weather conditions and provide Earth coverage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03740 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized Greedy Methods for Weak Submodular Sensor Selection with Robustness Considerations Kaya, Ege C. Hibbard, Michael Tanaka, Takashi Topcu, Ufuk Hashemi, Abolfazl Optimization and Control Systems and Control Signal Processing We study a pair of budget- and performance-constrained weak-submodular maximization problems. For computational efficiency, we explore the use of stochastic greedy algorithms which limit the search space via random sampling instead of the standard greedy procedure which explores the entire feasible search space. We propose a pair of stochastic greedy algorithms, namely, Modified Randomized Greedy (MRG) and Dual Randomized Greedy (DRG) to approximately solve the budget- and performance-constrained problems, respectively. For both algorithms, we derive approximation guarantees that hold with high probability. We then examine the use of DRG in robust optimization problems wherein the objective is to maximize the worst-case of a number of weak submodular objectives and propose the Randomized Weak Submodular Saturation Algorithm (Random-WSSA). We further derive a high-probability guarantee for when Random-WSSA successfully constructs a robust solution. Finally, we showcase the effectiveness of these algorithms in a variety of relevant uses within the context of Earth-observing low Earth orbit satellite constellations which estimate atmospheric weather conditions and provide Earth coverage. |
| title | Randomized Greedy Methods for Weak Submodular Sensor Selection with Robustness Considerations |
| topic | Optimization and Control Systems and Control Signal Processing |
| url | https://arxiv.org/abs/2404.03740 |