Lipschitz Continuous Algorithms for Covering Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909348466262016 |
|---|---|
| author | Kumabe, Soh Yoshida, Yuichi |
| author_facet | Kumabe, Soh Yoshida, Yuichi |
| contents | Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small perturbations in the input. Failure to do so can lead to several problems, including costly decisions, reduced user trust, potential security concerns, and lack of replicability. Unfortunately, many fundamental combinatorial algorithms are vulnerable to small input perturbations. To address the impact of input perturbations on algorithms for weighted graph problems, Kumabe and Yoshida (FOCS'23) recently introduced the concept of Lipschitz continuity of algorithms. This work explores this approach and designs Lipschitz continuous algorithms for covering problems, such as the minimum vertex cover, set cover, and feedback vertex set problems.
Our algorithm for the feedback vertex set problem is based on linear programming, and in the rounding process, we develop and use a technique called cycle sparsification, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_08213 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Lipschitz Continuous Algorithms for Covering Problems Kumabe, Soh Yoshida, Yuichi Data Structures and Algorithms Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small perturbations in the input. Failure to do so can lead to several problems, including costly decisions, reduced user trust, potential security concerns, and lack of replicability. Unfortunately, many fundamental combinatorial algorithms are vulnerable to small input perturbations. To address the impact of input perturbations on algorithms for weighted graph problems, Kumabe and Yoshida (FOCS'23) recently introduced the concept of Lipschitz continuity of algorithms. This work explores this approach and designs Lipschitz continuous algorithms for covering problems, such as the minimum vertex cover, set cover, and feedback vertex set problems. Our algorithm for the feedback vertex set problem is based on linear programming, and in the rounding process, we develop and use a technique called cycle sparsification, which may be of independent interest. |
| title | Lipschitz Continuous Algorithms for Covering Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2307.08213 |